No.434 占い

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 24
作問者 : 🐬hec🐬hec / テスター : koyumeishikoyumeishi

0 ProblemId : 467 / 出題時の順位表

問題文

みなさん,数字を使った占いというものをご存知でしょうか?
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
入力
1
3582
出力
8

問題文に書かれている例と同じです.

サンプル2
入力
10
0
1
2
3
4
5
6
7
8
9
出力
0
1
2
3
4
5
6
7
8
9

長さ1の数字列には何も処理する必要はありません.

サンプル3
入力
10
09
18
27
36
45
54
63
72
81
90
出力
9
9
9
9
9
9
9
9
9
9

九九表の9の段の10の位と1の位の和は必ず9なんですよ.

サンプル4
入力
10
3735193991
6406080286
5191117191
9096163630
2612780068
3850187272
6329054969
8747630709
5278943458
4022606808
出力
1
3
3
9
7
8
9
2
1
9

提出ページヘ