B. Partition Addition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. In one operation, you can split the digits of $$$n$$$ into two nonempty parts and replace $$$n$$$ with their sum. For example, if $$$n=12526$$$, you could split it into $$$125$$$ and $$$26$$$ and set $$$n = 125 + 26 = 151$$$, or if $$$n=10001$$$, you could split it into $$$1$$$ and $$$0001$$$ and set $$$n=1 + 0001 =2$$$.

If you can perform this operation any number of times (including zero), what is the minimum $$$n$$$ you can achieve?

Input

The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 10^5$$$) — the number of test cases.

Each test case consists of a single line containing an integer $$$n$$$ ($$$1\le n \le 10^9$$$) — the initial value of $$$n$$$.

Output

For each test case, print a single integer — the minimum possible value of $$$n$$$ after performing any number of operations.

Example
Input
5
12526
2
123456789
347347
1000000000
Output
7
2
9
1
1
Note

In the first test case, you can use this series of operations:

$$$$$$12526 \longrightarrow 125 + 26 = 151 \longrightarrow 1 + 51 = 52 \longrightarrow 5 + 2 = 7$$$$$$

In the second test case, since $$$n$$$ only has one digit, it is impossible to perform any operations.