2041: [USACO 2024 December Contest, Bronze] Problem 1. Roundabout Rounding

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 ≥ 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² (hundred), Bessie would first locate the 2nd digit from the right which is 5. This means x=5. Then since x≥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², 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¹, then the nearest 10², 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≤N≤10⁹) 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≥x.

You have to answer multiple test cases.

The first line of input contains a single integer T (1≤T≤10⁵) denoting the number of test cases. T test cases follow.

The first and only line of input in every test case contains a single integer N. All N within the same input file are guaranteed to be distinct.

4
1
100
4567
3366

0
5
183
60