LKID  Identity crisis(Medium)
As lucky have solved IDC1948 with easy constraints .Now he would like to solve the problem with some serious constraints 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 (0
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
1Explanation:$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
Anchrondite:
20150405 15:20:51
@ Lakshman why the solution with n^0.25 complexity giving TLE?


Sahil Sharma:
20150111 12:24:37
Could someone please explain what Francky meant by "pbC", "pbF" and "pbA"?


[Lakshman]:
20150111 12:24:37
Thanks @Francky for clarification. I have moved LCMSUMH to tutorial, But I am leaving this LKID to Classical section. 

Francky:
20150111 12:24:37
Yes, the original problem has weak constraints and had some issues at time of publications ; it's not the best problem...


Mitch Schwartz:
20150111 12:24:37
I'm pretty sure the 10^29 suggestion was ironic. :p Last edit: 20150102 08:53:12 

[Lakshman]:
20150111 12:24:37
@EB Members I will leave it on you. If you think both are duplicate problems you can move it to tutorial. 

Min_25:
20150111 12:24:37
In fact, your problems LKID and LCMSUMH are the almost duplicates of FACT1 for those who have solved the original problems. Last edit: 20150102 04:40:42 

Francky:
20150111 12:24:37
I don't think this edition need a better specific algorithm than the original, where brute force can't pass. It's true, the first have low constraints and it's easy to get 0.00s even with slow languages, but this one only need a non specific part of code...


anurag garg:
20150111 12:24:37
Lakshman can you tell me what is wrong in my last submission.


legrand:
20150111 12:24:37
@Lakshman  what's wrong in my submission 12394776

Added by:  [Lakshman] 
Date:  20140325 
Time limit:  1s6s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IDC1948 