/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 番目のテストケースに対する答えを出力してください。
入力例 1
3 1412 23 498650499498649123
出力例 1
1313 22 498650498650498650
1 個目のテストケースについて、 1412 以下の「周期的な数」にはたとえば 11,\ 222,\ 1212,\ 1313 などが考えられますが、このうち最大のものは 1313 です。
Score : 400 points
Problem Statement
For a positive integer n, let \mathrm{str}(n) be the string representing n in decimal.
We say that a positive integer n is periodic when there exists a positive integer m such that \mathrm{str}(n) is the concatenation of two or more copies of \mathrm{str}(m). For example, 11, 1212, and 123123123 are periodic.
You are given a positive integer N at least 11. Find the greatest periodic number at most N. It can be proved that there is at least one periodic number at most N.
You will get T test cases to solve.
Constraints
- 1 \leq T \leq 10^4
- 11 \leq N < 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is given in the following format:
N
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 1412 23 498650499498649123
Sample Output 1
1313 22 498650498650498650
For the first test case, the periodic numbers at most 1412 include 11, 222, 1212, 1313, and the greatest is 1313.