Problem Statement

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ᵇ (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ᵇ 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ᵇ​, Elsie will first round to the nearest ​10¹​, then the nearest ​10²​, and so on until the nearest ​10ᵇ​.

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ᵖ is different than chain rounding to the nearest ​10ᵖ​, where P is the smallest integer such that ​10ᵖ≥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≤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.

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:

plaintext

4
1
100
4567
3366

SAMPLE OUTPUT:

plaintext

0
5
183
60

Consider the second test case in the sample. 48 should be counted because 48 chain rounded to the nearest 10² is 100 (​48→50→100​), but 48 rounded to the nearest 10² 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²​.

SCORING:

• Inputs 2-4: ​N​≤10³
• Inputs 5-7: ​N​≤10⁶
• Inputs 8-13: No additional constraints.

Problem credits: Weiming Zhou