# 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. **Share**Code). 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 4Submit

Source: 12th Iran Nationwide Internet Contest IV