問題文

概要：文字列 $S$ が与えられます。圧縮後の文字列が最短となるように連長圧縮してください。

• 以下の手順によって $B$ から生成される文字列が $A$ と一致する。
1. 整数 $k$ および $k$ 個の非空な英文字列 $u_1, u_2, \dots, u_k$ および $k$ 個の非空な数字列 $v_1, v_2, \dots, v_k$ であって、 $u_1 v_1 u_2 v_2 \dots u_k v_k$ が $B$ と一致するものを取り出す。
   (このような $k, u_1, \dots, u_k, v_1, \dots, v_k$ は存在すれば一意に定まることが証明できる。)
   条件を満たす $k, u_1, \dots, u_k, v_1, \dots, v_k$ が存在しない場合は、文字列を生成することなく手順を終了する。
2. 文字列 $C$ を空文字列とする。$i = 1, 2, \dots, k$ の順に以下の操作を行う。
   • $v_i$ を 10 進表記された数とみなしたときの値を $x$ とする。$C$ の末尾に $u_i$ を追加する操作を $x$ 回行う。
3. 2. の操作を終えた後の $C$ を手順によって生成される文字列とする。

制約

• $1 \leq T \leq 5 \times 10^5$
• $S$ は英小文字からなる長さ $5 \times 10^5$ 以下の文字列
• 全ての入力をわたる $|S|$ の総和は $5 \times 10^5$ を超えない。

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

$S$

出力

$T$ 行出力せよ。$i$ 行目には $i$ 番目のテストケースへの答えを出力せよ。また、最後に改行せよ。
なお、答えが複数ある場合はどれを出力してもよい。

サンプル

7
aabababc
abcdef
abaababaabaab
aaaaaaaaa
aaaaaaaaaa
baaaaaaaaa
baaaaaaaaaa

a1ab3c1
abcdef1
abaab2aab1
a9
a10
b1a9
ba1a9