Limits 1s, 512 MB

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 NN, Alice wants to find the maximum digit sum among all the divisors of NN. 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 NN is any positive integer that evenly divides NN without leaving a remainder. Your goal is to find the divisor of NN that yields the highest sum of its digits. For example, consider the number 2424. The divisors of 2424 are 1,2,3,4,6,8,121, 2, 3, 4, 6, 8, 12, and 2424. The sum of digits for each divisor is as follows:

  • 1:11: 1

  • 2:22: 2

  • 3:33: 3

  • 4:44: 4

  • 6:66: 6

  • 8:88: 8

  • 12:1+2=312: 1 + 2 = 3

  • 24:2+4=624: 2 + 4 = 6

In this case, the maximum sum of digits among the divisors of 2424 is 88.

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

Input

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

Each of the next TT lines contains a positive integer NN (1N106)(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 NN.

Sample

InputOutput
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.

Submit

Login to submit.

Statistics

93% Solution Ratio
ItzRAYEarliest, 10M ago
user.4356Fastest, 0.0s
dodo_codoLightest, 4.9 MB
ItzRAYShortest, 532B
Toph uses cookies. By continuing you agree to our Cookie Policy.