- All Contests
- ProjectEuler+
- Project Euler #159: Digital root sums of factorisations.

# Project Euler #159: Digital root sums of factorisations.

# 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**

```
51
```

**Explanation**