Mysterious ritual#11031

Mysterious ritual

1 second

128 megabytes

Medium

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 \leq t \leq 1 0^{5}$ 1 \le t \le 10^5). Each of the next $t$ lines contains a single integer $n_{i}$ n_i ( $1 \leq n_{i} < 1 0^{500001}$ 1 \le 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.

Examples

Example 1

Loading

1 \leq t \leq 1 0^{5}

n_{i}

1 \leq n_{i} < 1 0^{500001}