1. 

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #256 (Quirksome Squares)
* http://icpcres.ecs.baylor.edu/onlinejudge/external/2/256.pdf
*
* @author Christian Posselt
* @author Jonathan Schubert
* @version 1.1, 03/29/2009
*
* Status : Accepted
* Runtime: 1.050
*/
import java.io.*;


class QuirksomeSquares256
{
public static void main(String[] args) throws IOException
{
BufferedReader Reader = new BufferedReader(new InputStreamReader(System.in));
final int[] Power = new int[] {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

while(true) //Read all the lines
{
String line = Reader.readLine();
if(line == null) //all user input is read
break;
int digits = Integer.parseInt(line);
if(digits % 2 != 0) //invalid user input
throw new RuntimeException();

int testdigits = digits/2;
for(int counterhigh = 0; counterhigh < Power[testdigits]; counterhigh ++) //high counter for testing
{
//Compute parts of the formula just if they are chaining
int APow = counterhigh * counterhigh; //compute parts of the formula just every n/2 digits: a^2
int AHigh = counterhigh * Power[testdigits];//compute parts of the formula just every n/2 digits: a*n n = number of digits / 2
int ADopple = 1 - counterhigh* 2; //compute parts of the formula just every n/2 digits: (1 - 2a)
for (int counterlow = 0; counterlow < Power[testdigits]; counterlow ++) //low counter for testing
{
//Formula = (a + b)^2 = a*n+b n = half of the digits^10 A
// a^2 + b^2 = a*n + b - 2ab
// a^2 + b^2 = a*n + b(1 - 2a)
// APow + b*b = AHigh+b*ADopple
if(APow + counterlow*counterlow == AHigh+counterlow*ADopple)
{
System.out.printf("%0"+testdigits+"d%0"+testdigits+"d%n",counterhigh,counterlow);
}
}
}
}
}
}