Big Password

Time Limit: 5 Seconds    Memory Limit: 32768 KB

You know that, nowadays, in each website a pair of username and password is required (e.g. ShareCode). However, I have a bad habit!!! I can only choose the passwords, which are integers generated by concatenation of the sequence of the numbers 1 to n. In addition, the generated big integer should be divisible by (n+1) (e.g. 12 Mod 3=0 and 12345678 Mod 9 =0). I like the values of n, which can generate such passwords for me. In order to convince me to break that habit; you are going to show me how many passwords are there for values of n not greater than N.

Input

The input is started by an integer 0<t≤20 followed by t test cases. Each test case is represented by one line containing the integer N≤100,000.

Output

For each test case, output in a separate line, the number of passwords can be generated by all values of n≤N.

Sample Input

4
1
10
100
1000

Sample Output

0
2
4
4

Submit

Source: 12th Iran Nationwide Internet Contest IV