The digital root of a number x is calculated by summing up all digits x, then adding all digits of the sum and so on, until we are left with only a single digit.

For example, if x = 987654, then its digital root d(x) = 9 + 8 + 7 + 6 + 5 + 4 = 39. 

Now we sum up digits of 39. d(39) = 3 + 9 = 12.

Now we sum up digits of 12. d(12) = 1 + 2 = 3.

Thus, d(987654) = 3.

Input

The first line gives the number of test cases T (T <= 100).

Each of the next T test cases gives the value of N (N <= 50,000).

Output

For each test case, print 10 integers, each separated by a space, indicating number of digital roots in the range of 1 to N that are equal to i (1 <= i <= 9). Seperate each test case with a new line.

Example

Input:
2
12
40
 
Output:
2 2 2 1 1 1 1 1 1
5 5 5 5 4 4 4 4 4

Explanation:

For the first case, there are 2 numbers in the range of 1 to 12 that have digital root equal to 1 (1 and 10), 2 numbers that have digital root equal to 2 (2 and 11) and so on.