Digital Square
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 743 Accepted Submission(s): 139

Problem Description
Given an integer N,you should come up with the minimum nonnegative integer M.M meets the follow condition: M2%10x=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 <=109), indicating the given number. Output For each case output the answer if it exists, otherwise print None. Sample Input 3 3 21 25 Sample Output None 11 5

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 ``` ```#include #include #include #include #include #include   using namespace std;   int n; long long ans = 10000000000LL;   long long dfs(long long shi, long long now){ if(shi > n) return 0; int sheng = n % shi; for(long long i = 0; i <= 9; i ++){ long long a = i * shi + now; long long aa = a * a % (shi * 10); long long nn = n % (shi * 10); if(aa == nn){ //printf("a=%I64d aa=%I64d shi=%I64d\n", a, aa, shi); if(aa == n){ ans = min(ans, a); } else dfs(shi * 10, a); } } return 0; }   int main(){ int t; scanf("%d", &t); while(t --){ ans = 10000000000LL; scanf("%d", &n); if(n == 0){ printf("0\n"); continue; } if(n == 1000000000){ printf("None\n"); continue; } dfs(1, 0); if(ans == 10000000000LL) printf("None\n"); else printf("%I64d\n", ans); } return 0; }```