Ninja has an integer ‘N’. Ninja is fond of digit ‘1’ so Ninja wants to know the number of 1s in each number from 0 to N.

Your task is to help the Ninja in finding out the number of ones from 0 to ‘N’.

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first and only line of the test case consists of a single integer ‘N’.

Output Format

Return the total number of one digit.

Constraints

1 <= ‘T’ <= 11
1 <= ‘N’ <= 5000

Time Limit: 1 sec

Note:

 You do not need to print anything, it has already been taken care of. Just implement the given function.