IDC1948 - Identity crisis

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 Zp, where x(n) ≡ n (mod p).

Input

First line of input contains 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)


Added by:Konrad Krystecki
Date:2014-02-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-02-05 11:42:18 Konrad Krystecki
The ring (mathematics).
2014-02-05 11:42:18 Bhavik
what does Zp mean here??
2014-02-05 11:42:18 Konrad Krystecki
Thought you have TLE, not WA?
2014-02-05 11:42:18 vank
explain the first test case..
any tricky test case pls..

Last edit: 2014-02-05 09:13:00
2014-02-05 11:42:18 Konrad Krystecki
The test data.
Before rejudging they were incorrect sometimes.

Last edit: 2014-02-05 08:39:49
2014-02-05 11:42:18 vank
what better..
first they accepted my ans got good score and then showing WA

Last edit: 2014-02-05 08:37:09
2014-02-05 11:42:18 Konrad Krystecki
Now they seems to be better ;).
2014-02-05 11:42:18 Mitch Schwartz
For clarity, "x(n)=n mod p" means "x(n) ≡ n (mod p)". But there seems to be an error in the test data.

Last edit: 2014-02-05 02:43:52
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.