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 |