Roundabout Rounding timer 1s memory 1024MB

Bessie the cow is back in school! She has started doing her math homework in which she is tasked to round positive integers to powers of 10.

To round a positive integer a to the nearest 10^b, where b is a positive integer, Bessie first locates the b'th digit from the right. Let x denote this digit.

If x \geq 5, Bessie adds 10^b to a.

Then, Bessie sets all the digits including and to the right of the b'th digit from the right to be 0.

For instance, if Bessie wanted to round 456 to the nearest 10^2 (hundred), Bessie would first locate the 2nd digit from the right which is 5. This means x = 5. Then since x \geq 5, Bessie adds 100 to a. Finally, Bessie sets all the digits in a to the right of and including the 2nd digit from the right to be 0, resulting in 500.

However, if Bessie were to round 446 to the nearest 10^2, she would end up with 400.

After looking at Bessie's homework, Elsie thinks she has invented a new type of rounding: chain rounding. To chain round to the nearest 10^b, Elsie will first round to the nearest 10^1, then the nearest 10^2, and so on until the nearest 10^b.

Bessie thinks Elsie is wrong, but is too busy with math homework to confirm her suspicions. She tasks you to count how many integers x at least 2 and at most N (1 \leq N \leq 10^{9}) exist such that rounding x to the nearest 10^P is different than chain rounding to the nearest 10^P, where P is the smallest integer such that 10^P \geq x.