eolymp
bolt
Try our new interface for solving problems
Problems

Assignment of Nicholas

Assignment of Nicholas

Time limit 1 second
Memory limit 64 MiB

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 data

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 data

For each of the numbers given by Nicholas to his disciples, indicate its quality.

Examples

Input example #1
1
970481
Output example #1
30
Author Mark_tven