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 10b, 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 10b 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 102 (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 102, 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 10b, Elsie will first round to the nearest 101, then the nearest 102, and so on until the nearest 10b.
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≤109) exist such that rounding x to the nearest 10P is different than chain rounding to the nearest 10P, where P is the smallest integer such that 10P≥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≤T≤105) 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 102 is 100(48→50→100), but 48rounded to the nearest 102 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 67rounded to the nearest 102.
SCORING:
Inputs 2-4: N≤103
Inputs 5-7: N≤106
Inputs 8-13: No additional constraints.
Problem credits: Weiming Zhou
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
