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

Input

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

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