問題文

正整数 $n$ に対し、$n$ を十進法表記した文字列を $\\mathrm{str}(n)$ で表します。

正整数 $n$ について、ある正整数 $m$ が存在して $\\mathrm{str}(n)$ が $\\mathrm{str}(m)$ を $2$ 個以上連結したものになっているとき、 $n$ は「周期的な数」であるといいます。たとえば $11,\\ 1212,\\ 123123123$ は「周期的な数」です。

$11$ 以上の正整数 $N$ が与えられます。 $N$ 以下の「周期的な数」の最大値を求めてください。 $N$ 以下の「周期的な数」は $1$ つ以上存在することが示せます。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1 \\leq T \\leq 10^4$
• $11 \\leq N < 10^{18}$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

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

各ケースは以下の形式で与えられます。

$N$

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

入力例 1

3
1412
23
498650499498649123

出力例 1

1313
22
498650498650498650

$1$ 個目のテストケースについて、 $1412$ 以下の「周期的な数」にはたとえば $11,\\ 222,\\ 1212,\\ 1313$ などが考えられますが、このうち最大のものは $1313$ です。