Question
Count Core Values of Codes
For example, the core value of 799 is found by calculating 7 + 9 + 9 = 25, then 2 + 5 = 7. So, the core value of 799 is 7. Your task is to determine how many codes have core values from 1 to 9, and print the count for each.
You are given a list of N mysterious codes, each represented by a number. Your task is to unlock the core value of each code by performing a sequence of steps:
- Add up all the digits of the code.
- If the result is a single-digit number (less than 10), that is the core value, and the process stops.
- If the result is 10 or greater, continue by adding the digits of the new number until you get a single-digit core value.
For example, the core value of 799 is found by calculating 7 + 9 + 9 = 25, then 2 + 5 = 7. So, the core value of 799 is 7. Your task is to determine how many codes have core values from 1 to 9, and print the count for each.
Input
First line of the input contains a single integer N, denoting the size of array.
Second line of the input contains N space-separated numbers, denoting the element of an array.
Constraints
1 ≤ N ≤ 105
1 ≤ A[i].length ≤ 105
Sum of lengths of A[i] over all i from 1 to N doesn't exceed 5x105.
The array elements can be too large, so they will be provided in the form of string.
Second line of the input contains N space-separated numbers, denoting the element of an array.
Constraints
1 ≤ N ≤ 105
1 ≤ A[i].length ≤ 105
Sum of lengths of A[i] over all i from 1 to N doesn't exceed 5x105.
The array elements can be too large, so they will be provided in the form of string.
Output
Print 9 integers B1, B2,. , B9 where Bi is the number of integers Ai whose Core Value is i.
Example
Sample Input
5
79752 12793 13471 31973 113
Sample Output
0 0 1 1 2 0 1 0 0
Explanation
Core Value of 79752 = 7 + 9 + 7 + 5 + 2 = 30 = 3 + 0 = 3
Core Value of 12793 = 1 + 2 + 7 + 9 + 3 = 22 = 2 + 2 = 4
Core Value of 13471 = 1 + 3 + 4 + 7 + 1 = 16 = 1 + 6 = 7
Core Value of 31973 = 3 + 1 + 9 + 7 + 3 = 23 = 2 + 3 = 5
Core Value of 113 = 1 + 1 + 3 = 5
5
79752 12793 13471 31973 113
Sample Output
0 0 1 1 2 0 1 0 0
Explanation
Core Value of 79752 = 7 + 9 + 7 + 5 + 2 = 30 = 3 + 0 = 3
Core Value of 12793 = 1 + 2 + 7 + 9 + 3 = 22 = 2 + 2 = 4
Core Value of 13471 = 1 + 3 + 4 + 7 + 1 = 16 = 1 + 6 = 7
Core Value of 31973 = 3 + 1 + 9 + 7 + 3 = 23 = 2 + 3 = 5
Core Value of 113 = 1 + 1 + 3 = 5