Quirksome Squares

The number 3025 has a remarkable quirk: if you split its decimal representation in two strings of equal length (30 and 25) and square the sum of the numbers so obtained, you obtain the original number:

The problem is to determine all numbers with this property having a given even number of digits.

For example, 4-digit numbers run from 0000 to 9999. Note that leading zeroes should be taken into account. This means that 0001 which is equal to is a quirksome number of 4 digits. The number of digits may be 2,4,6 or 8. Although maxint is only 32767 and numbers of eight digits are asked for, a well-versed programmer can keep his numbers in the range of the integers. However efficiency should be given a thought.

Input

The input of your program is a textflle containing numbers of digits (taken from 2,4,6,8), each number on a line of its own.

Output

The output is a textfile consisting of lines containing the quirksome numbers (ordered according to the input numbers and for each input number in increasing order).

Warning: Please note that the number of digits in the output is equal to the number in the corresponding input line : leading zeroes may not be suppressed.

Sample Input

2
2

Sample Output

00
01
81
00
01
81

#include <stdio.h>
#include <string.h>
int main() {
	int n, i, a, b;
	char s1[10], s2[10];
	while(scanf("%d", &n) == 1) {
		int l1 = 1, l2 = 1;
		for(i = 0; i < n; i++)
			l1 *= 10;
		for(i = 0; i < n/2; i++)
			l2 *= 10;
		for(i = 0; i < l1; i++) {
			if(i*i >= l1)	break;
			a = i*i/l2, b = i*i%l2;
			if(n == 2 && (a+b)*(a+b) == i*i) {
				sprintf(s1, "%01d%01d", a, b);
				sprintf(s2, "%02d", i*i);
				if(strcmp(s1, s2) == 0)
					printf("%s\n", s2);
			}
			if(n == 4 && (a+b)*(a+b) == i*i) {
				sprintf(s1, "%02d%02d", a, b);
				sprintf(s2, "%04d", i*i);
				if(strcmp(s1, s2) == 0)
					printf("%s\n", s2);
			}
			if(n == 6 && (a+b)*(a+b) == i*i) {
				sprintf(s1, "%03d%03d", a, b);
				sprintf(s2, "%06d", i*i);
				if(strcmp(s1, s2) == 0)
					printf("%s\n", s2);
			}
			if(n == 8 && (a+b)*(a+b) == i*i) {
				sprintf(s1, "%04d%04d", a, b);
				sprintf(s2, "%08d", i*i);
				if(strcmp(s1, s2) == 0)
					printf("%s\n", s2);
			}
		}
	}
    return 0;
}