bjfu---1196fudq and Digital

描述

The other day, AC Goddness asked fudq for help as she was in trouble in a easy problem.The problem requires to find the minimum nonnegative integer M when given an integer N.M meets this condition:
(M^2)%(10^x)=N (x=0,1,2,3...).
fudq don't want to lose face in front of AC Goddness.So can you help fudq?

输入

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 <= 1,000,000,000), indicating the given number.

输出

For each case output the answer if it exists, otherwise print “Sorry, I tried.”.

样例输入

3
3
21
25

样例输出

Sorry, I tried.
11
5

提示

M^2 = M*M;

Code:

#include <stdio.h>