如果一个数字 $b$ 可以通过删除数字 $a$ 十进制表示中的部分（但不能全部）数字，并保持剩余数字的顺序不变而得到，则称 $b$ 是 $a$ 的子序列。例如，356 是 1234567 的子序列，因为你可以删除 1、2、4 和 7 得到 356。然而，0 不是 23527 的子序列，因为 23527 中不存在数字 0。

给定一个数字 $x$。请找到任意一个数字 $n$，使得 $n$ 的所有子序列构成的集合的 MEX 等于 $x$。可以证明这样的 $n$ 总存在。

集合的 MEX 定义为该集合中未出现的最小非负整数。例如，$\{0, 1, 2, 4\}$ 的 MEX 是 3，$\{1, 4, 6, 8\}$ 的 MEX 是 0。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例包含一行，为一个整数 $x$ ($1 \le x < 10^{10000}$)，即所需的子序列 MEX 值。保证 $x$ 不包含前导零。

保证所有测试用例中 $x$ 的位数之和不超过 10000。

输出格式

对于每个测试用例，输出一个正整数 $n$，即任意一个满足其子序列 MEX 为 $x$ 的数字。$n$ 不能包含前导零。

如果存在多个解，输出任意一个即可。

所有测试用例中 $n$ 的位数之和必须不超过 $10^6$。

样例

输入 1

4
1
9
10
22

输出 1

70
12836880457
2468013579
12013456789

说明

在第一个样例中，70 的子序列为 7、0 和 70，集合 $\{0, 7, 70\}$ 的 MEX 为 1。

在第二个样例中，12836880457 包含了除 9 以外的所有数字，因此其子序列的 MEX 为 9。