This problem is a programming version of Problem 159 from projecteuler.net
A composite number can be factored many different ways.
For instance, not including multiplication by one, can be factored in distinct ways:
Recall that the digital root of a number, in base , is found by adding together the digits of that number, and repeating that process until a number is arrived at that is less than .
Thus the digital root of is .
We shall call a Digital Root Sum () the sum of the digital roots of the individual factors of our number.
The chart below demonstrates all of the values for .
The maximum Digital Root Sum of is .
The function gives the maximum Digital Root Sum of . So .
Find .
Input Format
First line of each file contains an integer which is the number of testcases.
lines follow, each containing one integer .
Constraints
Output Format
Output lines, one for each testcase.
Sample Input
1
10
Sample Output
51
Explanation