DIGRT - Digital Root Counter

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.

 

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.


Added by:.:: Pratik ::.
Date:2010-04-16
Time limit:1.258s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET

hide comments
2011-03-28 21:36:47 brahiam
using System;


namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{


long a, b;
long suma=0;

a = Convert.ToInt64(Console.ReadLine());
b = Convert.ToInt64(Console.ReadLine());

if (T <= 100&& N <= 50,000)
a += b;


Console.WriteLine(a);
Console.Read();

}
}
}
2010-04-19 10:55:44 Andrey Maksimenko
Instead of
"For each test case, print 10 integers"
should be
"For each test case, print 9 integers"
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.