import java.math.BigInteger;

public class ImmortSchnittmengeCount {

	public static final int MAX_NUM = 1000000;
	public static final int MAX_BASE = 10000;

	public static String convertToAnyBase(BigInteger num, BigInteger base) {
		StringBuilder res = new StringBuilder();

		while (true) {
			BigInteger[] qr = num.divideAndRemainder(base);
			BigInteger div = qr[0];
			BigInteger mod = qr[1];

			res.insert(0, "(" + mod + ")");
			if (div.equals(BigInteger.ZERO)) {
				break;
			}

			num = div;
		}

		return res.toString();
	}

	public static boolean isImmortal(BigInteger num, BigInteger base) {
		BigInteger num2 = num.pow(2);

		String a = convertToAnyBase(num, base);
		String b = convertToAnyBase(num2, base);

		return b.endsWith(a);
	}

	public static void main(String[] args) throws Exception {
		for (int num = 2; num <= MAX_NUM; num++) {
			int count = 0;
			for (int base = 2; base <= MAX_BASE; base++) {
				if (isImmortal(BigInteger.valueOf(num), BigInteger
						.valueOf(base))) {
					count++;
				}
			}
			System.out.println("Zahl\t" + num + "\tbei Basis 2.." + MAX_BASE
					+ " ist Unsterblich\t" + count + "\tMale.");
		}
	}

}