Problem Statement

Everyone, have you heard of fortune telling using digits?
The following operations are performed on a digit string $S=s_1,s_2,\dots,s_N$ consisting of the digits 0-9.

1. Let the length of the digit string $S$ be $K$. If $K=1$, terminate.
2. For two adjacent digits $s_i,s_{i+1}$ ($1\le i \le K-1$) of the digit string, let their sum be $s'_i$.
3. If $s'_i \ge10$, replace it with the sum of its tens digit and its ones digit.
4. Replace $S$ as $S=s'_1,s'_2,\dots,s'_{K-1}$.
5. Return to operation 1.

The single digit obtained by these operations tells your fortune.

For example, when the operations are performed on the digit string $S=3,5,8,2$, the digit string S changes as follows.
$S=3,5,8,2$
$S=8,4,1$
$S=3,5$
$S=8$
In this case, the digit finally obtained is 8.

I thought of performing this fortune telling, but I soon realized that it is impossible to compute by hand.
So, given a digit string $S$, please find the result of the fortune telling.

Input

$T$
$S_1$
$S_2$
$\vdots$
$S_T$

The first line contains the number of test cases T. $1\le T \le 10^3$
Each test case consists of one line, containing a digit string $S_i$. $1\le i \le T$
Here, $|S_i|$ denotes the length of the digit string $S_i$.

The input satisfies the following constraints.
$1 \le |S_i| \le 10^3, \sum_{i=1}^{T} |S_i| \le 10^3$

Output

For each test case, output the fortune telling result of the digit string $S_i$ on one line.

Sample

1
3582

8

10
0
1
2
3
4
5
6
7
8
9

0
1
2
3
4
5
6
7
8
9

10
09
18
27
36
45
54
63
72
81
90

9
9
9
9
9
9
9
9
9
9

10
3735193991
6406080286
5191117191
9096163630
2612780068
3850187272
6329054969
8747630709
5278943458
4022606808

1
3
3
9
7
8
9
2
1
9