Assignment of Nicholas
Approaching New Year! Third graders are already dreaming to go near the Christmas tree in Kiev. Teacher of Mathematics, one with a 3-class city of Alexandria, they were informed that she could took on tree in Kiev only those students who solve puzzle of St. Nicholas. He wants to know the quality of a given number.
According to Nicholas, the quality of the number N is the sum of digits of all positive integers A is not very large number N such that the remainder of the division of N by the number of A is 0.
Input
The first line contains an integer N (N <= 100) – the number of students in the 3 rd grade. In the nextN lines available jobs for each student: a natural number not more than 15 000 000 (Nicholas decided to spare the students and the number selected is not very large).
Output
For each of the numbers given by Nicholas to his disciples, indicate its quality.