Maximum Among Divisors

Alice is thrilled about participating in the “Take-off Programming Contest Spring 2023”, but she realizes that number theory is one of her weak areas. Determined to overcome this challenge, Alice dives into the study of number theory and learns about two crucial concepts: digit sum and divisors of a number. Empowered by her newfound knowledge, Alice devises a new problem to put her understanding to the test.

Given an integer $N$, Alice wants to find the maximum digit sum among all the divisors of $N$. However, Alice encounters difficulties and cannot solve the problem alone. Now, it's your task to help Alice find a solution.

Formally, a divisor of $N$ is any positive integer that evenly divides $N$ without leaving a remainder. Your goal is to find the divisor of $N$ that yields the highest sum of its digits. For example, consider the number $24$. The divisors of $24$ are $1, 2, 3, 4, 6, 8, 12$, and $24$. The sum of digits for each divisor is as follows:

• $1: 1$

• $2: 2$

• $3: 3$

• $4: 4$

• $6: 6$

• $8: 8$

• $12: 1 + 2 = 3$

• $24: 2 + 4 = 6$

In this case, the maximum sum of digits among the divisors of $24$ is $8$.

Write a program that can efficiently solve this problem for various test cases.

Input

The first line of the input contains an integer $T$ $(1 \le T \le 10^4)$ — representing the number of test cases.

Each of the next $T$ lines contains a positive integer $N$ $(1 \le N \le 10^{6})$ — representing a test case.

Output

For each test case, output a single line with an integer — representing the maximum sum of digits among all the divisors of $N$.

Sample

Input	Output
4 12 9 34 22	6 9 8 4

As the numbers involved can be large and have multiple test cases, ensure that your solution runs efficiently within the given constraints.

Be careful about the new line (‘\n’) at the end.