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 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
hide comments
azam_9:
20160719 20:34:37
300th on spoj..<3..CREDITS :@pulkit_gulati 

ROHIT GUPTA:
20160206 18:21:19
bad problem. two same solution with different header , giving ac in c WA in c++ 

gullu_mishra:
20151027 06:52:47
AC in 1 goo...easy one ..simple maths+sieve ;) 

kamran siddique:
20151021 11:53:08
Easy One... 

ROHIT RAJ:
20150928 05:32:51
AC in 1 go !!


deadbrain:
20150114 06:35:30
Very Poor Explanation.... Could have been much better.... Think beyond what is written and dont be distracted by the comments... 

D:
20150112 14:47:58
yupiee! finally solved. 

zicowa:
20140712 23:47:33
and also for 99 consider 99 

zicowa:
20140712 23:46:13
finally GOT AC go with the standard defination for modulo congurency and abs(ab) 

Anshul Singhal:
20140708 23:01:17
@Konrad Krystecki what is the x(n) for n=99.....Is it 900 or 0 ......Please reply fast Last edit: 20140708 23:09:21 
Added by:  Konrad Krystecki 
Date:  20140204 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 