問題文

みなさん，数字を使った占いというものをご存知でしょうか?
0-9の数字で構成された数字列$S=\{ s_1,s_2,\dots,s_N \}$に対して以下の操作を行います．

1. 数字列$S$の長さを$K$とする．$K=1$ならば終了する．
2. 数字列$S$の隣り合った2つの数字$s_i,s_{i+1}$ ($1\le i \le K-1$)の和を$s'_i$とする．
3. $s'_i \ge10$の場合は10の位と1の位を足して置き換える． (例 $s'_i=13$の場合は $s'_i=1+3=4$と置き換える．)
4. $S=\{ s'_1,s'_2,\dots,s'_{K-1} \}$として置き換える．
5. 1の操作に戻る．

この操作で得られた1つの数字により運勢が分かるというものです．

例えば，数字列$S=\{ 3,5,8,2 \}$の場合について操作を行うと数字列Sは以下のように変化します．
$S=\{ 3,5,8,2 \}$
$S=\{ 8,4,1 \}$
$S=\{ 3,5 \}$
$S=\{ 8 \}$
この場合，最終的に得られる数字は8となります．

この占いを行うと考えましたが，手計算するのは無理だとすぐに分かりました．
そこで，数字列$S$が与えられるので占いの結果を求めてください．

入力

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

1行目にテストケースの数Tが与えられる．$1\le T \le 10^5$
各テストケースは1行からなり，数字列$S_i$が与えられる．$1\le i \le T$
ここで，$|S_i|$は数字列$S_i$の長さを表します．

入力は次の制約を満たします．
$1 \le |S_i| \le 10^5, \sum_{i=1}^{T} |S_i| \le 10^5$

出力

各テストケースごとに，数字列$S_i$の占い結果を1行で出力してください．

サンプル

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