周期数

时间限制：2s
空间限制：1024MB

题目描述

记正整数 $n$ 的十进制表示为 $\mathrm{str}(n)$。如果存在正整数 $m$，使 $\mathrm{str}(n)$ 是 $\mathrm{str}(m)$ 连续拼接至少两次得到的字符串，就称 $n$ 为周期数。例如 $11$、$1212$、$123123123$ 都是周期数。

给定正整数 $N\ge 11$，求不超过 $N$ 的最大周期数。保证答案存在。你需要回答 $T$ 组询问。

输入格式

第一行一个整数 $T$。接下来 $T$ 行，每行一个整数 $N$。

输出格式

输出 $T$ 行，每行给出对应询问的答案。

样例输入 1

3
1412
23
498650499498649123

样例输出 1

1313
22
498650498650498650

数据范围

对于所有数据，$1\le T\le 10^4$，$11\le N<10^{18}$。