問題文

yuki2006はレベルアップしてyuki2007になった．
このように文字列がレベルアップすると文字列に含まれる最後の非負整数が $1$ 増えます．
ここで言う，文字列に含まれる非負整数とは $0,1,2,3,4,5,6,7,8,9$ のみからなる部分文字列の中で極大の長さ（左右に伸ばせない）のものです．
もし，非負整数の先頭が $0$ から始まる場合は，$1$ 増えた後も桁数が変わらないようになります．
また，文字列に非負整数が含まれていなければ，レベルアップしても文字列は不変です．
文字列が与えられるので，レベルアップした後の文字列を求めてください．

入力

$1$ 行目にはテストケースの数 $T$ が与えられる．
各テストケースは $1$ 行のみからなり，文字列 $S$ が与えられる．

$1 \leq T \leq 20$
$1 \leq |S| \leq 100000 = 10^5$
$S$ はアスキーコード $32$ 以上 $126$ 以下の文字（全てprintableなものです）のみからなる

出力

各テストケースに対して，文字列 $S$ がレベルアップした後の文字列を $1$ 行で出力してください．

サンプル

5
yuki2006
rng_58
sugim48
02/29/2016
D programming language version 0.99

yuki2007
rng_59
sugim49
02/29/2017
D programming language version 0.100

7
hoge999hoge
73-23=49
O(n^2 log n)
hoge0003871hoge
00000000000000000000000
-0
piyo

hoge1000hoge
73-23=50
O(n^3 log n)
hoge0003872hoge
00000000000000000000001
-1
piyo