문제

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.

예제 입력 1

4
1
100
4567
3366

예제 출력 1

0
5
183
60

점수

Inputs 2-4: $N\le 10^3$Inputs 5-7: $N\le 10^6$Inputs 8-13: No additional constraints.