Problem Description

Given an integer N,you should come up with the minimum nonnegative integer M.M meets the follow condition: M²%10^x=N (x=0,1,2,3....)

Input

The first line has an integer T( T< = 1000), the number of test cases.
For each case, each line contains one integer N(0<= N <=10⁹), indicating the given number.

Output

For each case output the answer if it exists, otherwise print “None”.

3
3
21
25

None
11
5