bronze_Roundabout_Rounding — USACO December_Contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 9
Algorithms: mathematics

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 $2$nd 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 $2$nd 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$.
INPUT FORMAT (input arrives from the terminal / stdin):
You have to answer multiple test cases.
The first line of input contains a single integer $T$ ($1 \leq T \leq 10^5$)
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.
OUTPUT FORMAT (print output to the terminal / stdout):
Output $T$ lines, the $i$'th line containing the answer to the $i$'th test case.
Each line should be an integer denoting how many integers at least $2$ and at
most $N$ exist that are different when using the two rounding methods.
SAMPLE INPUT:
4
1
100
4567
3366
SAMPLE OUTPUT:
0
5
183
60
Consider the second test case in the sample. $48$ should be counted because $48$
chain rounded to the nearest $10^2$ is $100$ ($48\to 50\to 100$), but $48$
rounded to the nearest $10^2$ is
$0$.
In the third test case, two integers counted are $48$ and $480$. $48$ chain 
rounds to $100$ instead of to $0$ and $480$ chain rounds to $1000$ instead of
$0$.  However, $67$ is not counted since it chain rounds to $100$ which is $67$
rounded to the nearest $10^2$.
SCORING:
Inputs 2-4: $N\le 10^3$
Inputs 5-7: $N\le 10^6$
Inputs 8-13: No additional constraints.
Problem credits: Weiming Zhou

Starter code: