问题描述

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

当存在正整数 $m$，使得 $\\mathrm{str}(n)$ 是 $\\mathrm{str}(m)$ 的两个或多个拷贝的连接时，我们称正整数 $n$ 是 periodic。例如，$11$，$1212$ 和 $123123123$ 都是周期性的。

给定一个至少为 $11$ 的正整数 $N$。找到最大的周期性数，不超过 $N$。可以证明至少存在一个不超过 $N$ 的周期性数。

你将获得 $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

对于第一个测试用例，不超过 $1412$ 的周期性数包括 $11$，$222$，$1212$，$1313$，最大的是 $1313$。