题目描述

对于正整数 $n$，用 $\mathrm{str}(n)$ 表示 $n$ 的十进制表示字符串。

对于正整数 $n$，如果存在某个正整数 $m$，使得 $\mathrm{str}(n)$ 是 $\mathrm{str}(m)$ 连续连接 $2$ 次或更多次得到的字符串，则称 $n$ 是“周期性数”。例如，$11$、$1212$、$123123123$ 都是“周期性数”。

给定一个不小于 $11$ 的正整数 $N$，请你求出不超过 $N$ 的“周期性数”中的最大值。可以证明，不超过 $N$ 的“周期性数”至少有一个。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入以如下格式从标准输入读入：

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

每组数据格式如下：

$N$

输出格式

请输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。

样例 1

输入

3
1412
23
498650499498649123

输出

1313
22
498650498650498650

说明/提示

限制

• $1 \leq T \leq 10^4$
• $11 \leq N < 10^{18}$
• 输入的所有数均为整数

样例解释 1

对于第 $1$ 个测试用例，不超过 $1412$ 的“周期性数”有 $11$、$222$、$1212$、$1313$ 等，其中最大的为 $1313$。

由 ChatGPT 4.1 翻译