Problem Statement

yuki2006 leveled up and became yuki2007.
In this way, when a string levels up, the last non-negative integer contained in the string increases by $1$.
Here, a non-negative integer contained in a string means a substring of maximal length (one that cannot be extended to the left or right) among the substrings consisting only of $0,1,2,3,4,5,6,7,8,9$.
If the non-negative integer begins with $0$, the number of digits stays the same even after it increases by $1$.
Also, if the string contains no non-negative integer, the string remains unchanged when it levels up.
Given a string, find the string after it levels up.

Input

Line $1$ contains the number of test cases $T$.
Each test case consists of only $1$ line, which contains a string $S$.

$1 \leq T \leq 20$
$1 \leq |S| \leq 100000 = 10^5$
$S$ consists only of characters with ASCII codes between $32$ and $126$, inclusive (all of which are printable).

Output

For each test case, output the string obtained after the string $S$ levels up, on $1$ line.

Sample

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