IDC1948 - Identity crisis

no tags 

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 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 => 765234 mod 3

hide comments
azam_9: 2016-07-19 20:34:37

300th on spoj..<3..CREDITS :@pulkit_gulati

ROHIT GUPTA: 2016-02-06 18:21:19

bad problem. two same solution with different header , giving ac in c WA in c++

gullu_mishra: 2015-10-27 06:52:47

AC in 1 goo...easy one ..simple maths+sieve ;)

kamran siddique: 2015-10-21 11:53:08

Easy One...

ROHIT RAJ: 2015-09-28 05:32:51

AC in 1 go !!
Learned a lot. nice question

deadbrain: 2015-01-14 06:35:30

Very Poor Explanation.... Could have been much better.... Think beyond what is written and dont be distracted by the comments...

D: 2015-01-12 14:47:58

yupiee! finally solved.

zicowa: 2014-07-12 23:47:33

and also for 99 consider 99

zicowa: 2014-07-12 23:46:13

finally GOT AC go with the standard defination for modulo congurency and abs(a-b)

Anshul Singhal: 2014-07-08 23:01:17

@Konrad Krystecki what is the x(n) for n=99.....Is it 900 or 0 ......Please reply fast

Last edit: 2014-07-08 23:09:21

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