Background

在数字的浩瀚星空中，每个整数都蕴藏着独特的奥秘。在诸多奥秘之中， Pog 开始关注一种特殊的数字属性：数位和。对于一个正整数 n ，我们定义 S ( n )为其在十进制表示下的数位之和。例如， S (1729)=1+7+2+9=19. 现在， Pog 提出了一个有趣的数学问题：对于给定的正整数 n ，是否存在一个正整数 a ，使得 S ( n x a )= n x S ( a ）成立？(x为乘号)。 如果能解决这个谜题，那就更有趣了。请你帮助他找到一个可能的 a ，或者告诉他不可能存在解。 对于每组数据，若无解，输出"-1"，否则输出一个不大于1e9的正整数 a 表示一个合法的解。如果存在多解，输出一个最小的解。可以证明，若存在一个合法的解，则存在一个1e9以内的解。

Input

本题有多组数据。第一行一个整数 T (1≤ T ≤1e5）表示数据组数。 对于每组数据，输入为一行一个整数 n (1≤ n ≤1e9)。

Output

对于每组数据，若无解，输出"-1"，否则输出一个不大于1e9的正整数 a 表示一个合法的解。如果存在多解，输出一个值最小的解。可以证明，若存在一个合法的解，则存在一个1e9以内的解。

Samples

2  
1 
10

1
-1

Limitation

1s, 1024KiB for each test case.