問題文

みなさん，数字を使った占いというものをご存知でしょうか?
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^{\prime }$とする．
3. $s_i^{\prime }\ge 10$の場合は10の位と1の位を足して置き換える． (例 $s_i^{\prime }=13$の場合は $s_i^{\prime }=1+3=4$と置き換える．)
4. $S=\{s_1^{\prime },s_2^{\prime },\dots ,s_{K-1}^{\prime }\}$として置き換える．
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$
$⋮$
$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