配点 : $400$ 点

問題文

正整数 $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$ 番目のテストケースに対する答えを出力してください。

3
1412
23
498650499498649123

1313
22
498650498650498650

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