Project Euler #159: Digital root sums of factorisations.

_{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

Explanation