题目描述

给定一个正整数 $x$，你需要找到一个不超过 $10^{9}$ 的正整数 $y$，使得“$y^2$ 的十进制表示”中包含“$x$ 的十进制表示”，即如果把两个数的十进制表示看作两个字符串，后者可以作为前者的子串。

你需要处理 $T$ 次独立的询问，题目保证有解。

输入格式

第一行一个正整数 $T$，表示询问次数。

接下来 $T$ 行，每行包含一个正整数 $x$，即当前的询问。

输出格式

输出 $T$ 行，每行为一次询问的答案。

4
1
4
12
100

1
2
11
10

数据规模与约定

对于 $100\%$ 的数据，$1 \le T \le 100$，$1 \le x \le 10^7$。

• 子任务 1（30 分）：$1 \le x \le 9$。
• 子任务 2（30 分）：$1 \le x \le 100$。
• 子任务 3（40 分）：没有特殊限制。