Mysterious ritual
Kratos found a book that describes a mysterious ritual. Initially, you can choose any number n. You can do the following:
Remember the least significant digit of the number n in decimal notation.
Until n is completely divisible by 10, add the memorized digit.
Divide n by 10 and return to the beginning of the ritual.
The ritual continues indefinitely, the book says that the smallest number that will be equal to n during this ritual is magical. Kratos has not yet decided which initial n to choose. Help him determine the corresponding magic number for each initial option.
Input
The first line gives the number of tests t (1 ≤ t ≤ 10^5). Each of the next t lines contains a single integer n[i] (1 ≤ n[i] < 10^500001) - the initial value of n in the i-th test. The total length of numbers in all tests does not exceed 500000.
Output
For each test print one number on a new line - the minimum value that n will ever equal to during the ritual.