1.


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #636 - Squares (III)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=8&problem=577&mosmsg=Submission+received+with+ID+7132392
*
* @author Andre Wolfram
* @author Christoph Miesel
* @author Robert Seilbeck
* @version 1.0, 05/16/2009
*
* Status : Accepted
* Runtime 0.076
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));

String line;
while ((line = reader.readLine()) != null) {
if (line.equals("0")) {
break;
}
for (int base = 2; base <= 100; base++) {
long result = 0;
int exponent = 0;
for (int n = line.length() - 1; n >= 0; n--) {
// Zahl mit gegebener Basis errechnen
int number = Integer.parseInt(String
.valueOf(line.charAt(n)));
if (number < base) {
result += Math.pow(base, exponent) * number;
exponent++;
} else {
// 1 ist fluchtwert für zu kleine Basis
result = 1;
break;
}
}
if (1 != result) {
// Prüfen ob es sich um Wurzel handelt
int root = (int) Math.sqrt(result);
if (result == Math.pow(root, 2)) {
System.out.println(base);
break;
}
}
}

}

}

}