题目描述

在数字的浩瀚星空中，每个整数都蕴藏着独特的奥秘。在诸多奥秘之中，Pog 开始关注一种特殊的数字属性：数位和。对于一个正整数 $n$，我们定义 $S(n)$ 为其在十进制表示下的数位之和。例如，$S(1729) = 1 + 7 + 2 + 9 = 19$。

现在，Pog 提出了一个有趣的数学问题：对于给定的正整数 $n$，是否存在一个正整数 $a$，使得 $S(na) = nS(a)$ 成立？

如果能解决这个谜题，那就更有趣了。请你帮助他找到一个可能的 $a$，或者告诉他不可能存在解。

输入格式

本题有多组数据。第一行一个整数 $T(1 ≤ T ≤ 10⁵)$ 表示数据组数。

对于每组数据，输入为一行一个整数 $n(1 ≤ n ≤ 10⁹)$。

输出格式

对于每组数据，若无解，输出 -1，否则输出一个不大于 $10⁹$ 的正整数 $a$ 表示一个合法的解。

如果存在多解，输出任意一个不大于 $10⁹$ 的解。可以证明，若存在一个合法的解，则存在一个 $10⁹$ 以内的解。

2
3
10

3
-1