33062번 - 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 \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$.

입력

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 $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.

제한

힌트

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$.