As lucky have solved IDC1948 with easy constraints .Now he would like to solve the problem with some serious constraints. But as you know lucky is not very good in solving hard problems he need your help, can you help him.

For every given number n we define x(n) as distance from n to the first number greater than or equal to n in form of 99...99. For example x(100) = 899, x(45) = 54, etc. Given several n numbers you have to find the Zp, where x(n)≡n mod p.

Input

First  line of input  contains one number T (0 < T <  1001) - the number of test cases. In each of the next T lines contains one number each to represent n.

Output

In each line you have to write one number - the least p > 1 that x(n) ≡ n mod p. If there is no such p the line should contain -1.

Example

Input:
2
234
5

Output:
3
-1

Explanation

x(234) = 765. 765 mod 3 = 0, 234 mod 3 = 0 => 765 ≡ 234 mod 3

NOTE: Time limit is allowed to pass with slow languages.

My own C++ solution passed under 0.41s. Have fun;)