LKID - Identity crisis(Medium)

no tags 

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;)


hide comments
[Lakshman]: 2015-01-11 12:24:37

@kewlcoder Thanks statement updated.

bourne: 2015-01-11 12:24:37

@Lakshman - Shall the statement "For every given number n we define x(n) as distance from n to the first number after n in form of 99...99" not be read as "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" because "after n" implies greater than n ?

Anshul Singhal: 2015-01-11 12:24:37

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

--Lakshman-->of course 0.

Last edit: 2014-07-09 07:09:58
[Lakshman]: 2015-01-11 12:24:37

@All who are trying to solve this problem you need better complexity than O(sqrt(n)). sqrt(n) will TLE.

Last edit: 2014-04-03 10:45:30
anurag garg: 2015-01-11 12:24:37

whats wrong in my submission :11325756
thanks...
Lakshman-->Look at the constraints,after fixing it you will get TLE.your solution is too naive.

Last edit: 2014-03-25 18:34:52

Added by:[Lakshman]
Date:2014-03-25
Time limit:1s-6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IDC1948