Alice 和 Bob 在玩一个游戏： Alice 给出一个正整数 $x$，满足 $x<10^8$。

Bob 需要找出另一个正整数 $y$，满足 $y<10^9$，使得： 把 $x$ 和 $y$ 按顺序拼接成的新数 $x\#y$ 可以被 $x+y$ 整除。

其中 $x\#y$ 定义为：将整数 $x$ 与 $y$ 按先后顺序直接拼接得到的整数。 例如：$x=835,\ y=47$，则 $x\#y = 83547$。

题目保证：一定存在满足条件的 $y$。

输入格式

多组测试用例。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例组数。 每组仅一行，输入一个整数 $x$（$1\le x<10^8$）。

输出格式

对每组测试用例，输出一个满足条件的整数 $y$，要求： $1\le y<10^9$。 若有多组合法答案，输出任意一个即可。

样例输入

6
8
42
1000
66666
106344
9876543

样例输出

1
12
998
7872
8190
174036

样例说明

1. 第一组：$x=8$，取 $y=1$ 拼接数 $x\#y = 81$，和为 $x+y = 9$，满足 $81$ 能被 $9$ 整除。
2. 第二组：$x=42$，取 $y=12$ 拼接数 $x\#y = 4212$，和为 $x+y = 54$，满足 $4212$ 能被 $54$ 整除。