Problem Statement

Have you all heard of fortune telling using digits?
The following operations are performed on a digit sequence $S=\{ s_1,s_2,\dots,s_N \}$ consisting of the digits 0-9.

1. Let $K$ be the length of the digit sequence $S$. If $K=1$, terminate.
2. Let $s'_i$ be the sum of the two adjacent digits $s_i,s_{i+1}$ ($1\le i \le K-1$).
3. If $s'_i \ge10$, replace it with the sum of its tens digit and its ones digit. (For example, if $s'_i=13$, replace it with $s'_i=1+3=4$.)
4. Replace $S$ with $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, if the operations are performed on the digit sequence $S=\{ 3,5,8,2 \}$, the digit sequence 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 about doing this fortune telling, but I soon realized that calculating it by hand is impossible.
So, given a digit sequence $S$, 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^5$
Each test case consists of one line containing a digit sequence $S_i$. $1\le i \le T$
Here, $|S_i|$ denotes the length of the digit sequence $S_i$.

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

Output

For each test case, output the fortune telling result of the digit sequence $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