import java.util.ArrayList;
import java.util.Arrays;

public class LegrendeSymbol5p {
	public static void main(String[] args) {
		int[] primes = primes();
		for (Integer p : primes) {
			int[] legrendeValue = new int[p];
			for (int i = 1; i < p; i++) {
				long max = i * i;
				legrendeValue[mod((int) (max % p), p)] = 1;
			}
			for (int i = 1; i < p; i++) {
				if (legrendeValue[i] == 0) {
					legrendeValue[i] = -1;
				}
			}
			// This section is computing all possible values of t that satisfy
			// the constraints of Lemma 17.
			int[] inverses = computeInverses(p);
			ArrayList<Integer> tArray = new ArrayList<Integer>();
			ArrayList<Integer> excludedSet = new ArrayList<Integer>();
			excludedSet.add(0);
			excludedSet.add(1);
			excludedSet.add(2);
			excludedSet.add(3);
			excludedSet.add(4);
			excludedSet.add(p - 1);
			excludedSet.add(p - 2);
			excludedSet.add(p - 3);
			excludedSet.add(mod(inverses[2], p));
			excludedSet.add(mod(inverses[3], p));
			excludedSet.add(mod(inverses[4], p));
			excludedSet.add(mod(3 * inverses[2], p));
			excludedSet.add(mod(2 * inverses[3], p));
			excludedSet.add(mod(3 * inverses[4], p));
			excludedSet.add(mod(-3 * inverses[2], p));
			excludedSet.add(mod(-2 * inverses[3], p));
			excludedSet.add(mod(-3 * inverses[4], p));
			excludedSet.add(mod(-4 * inverses[3], p));
			excludedSet.add(mod(-inverses[2], p));
			for (int j = 0; j <= p - 1; j++) {
				boolean works = false;
				int check1 = mod(j + 1, p);
				int check2 = mod(9 - 16 * j, p);
				int check3 = mod(9 * j - 16, p);
				int check4 = mod((9 * j - 1) * (j - 1), p);
				int check5 = mod((j - 1) * (j - 9), p);
				int check6 = mod(j, p);
				if (legrendeValue[check1] == -1 && legrendeValue[check2] == -1 && legrendeValue[check3] == -1
						&& legrendeValue[check4] == -1 && legrendeValue[check5] == -1 && legrendeValue[check6] == 1
						&& !excludedSet.contains((Integer) j)) {
					tArray.add(j);
					works = true;
				}
				if (works) {
					System.out.println(p + ": t=" + tArray.get(0));
					break;
				}
			}
			if (tArray.size() == 0) {
				System.out.println(p + " doesn't work");
			}
		}

	}

	public static int mod(int a, int p) {
		return (a % p + p) % p;
	}

	public static boolean isPrime(int a) {
		for (int i = 2; i * i <= a; i++) {
			if (a % i == 0)
				return false;
		}
		return true;
	}

	public static int[] primes() {
		ArrayList<Integer> result = new ArrayList<Integer>();
		for (int i = 200; i <= 50000; i++) {
			if (isPrime(i)) {
				result.add(i);
			}
		}
		int[] output = new int[result.size()];
		for (int i = 0; i < result.size(); i++) {
			output[i] = result.get(i);
		}
		System.out.println("Prime Calculuation is Done");
		return output;
	}

	public static int[] computeInverses(int p) {
		int[] result = new int[p];
		for (int i = 0; i < p; i++) {
			result[i] = power(i, p - 2, p);
		}
		return result;
	}

	public static int power(int a, int k, int p) {
		int temp;
		if (k == 1)
			return a;
		if (k == 2)
			return ((a * a) % p);
		if (k % 2 == 0) {
			temp = power(a, k / 2, p);
			return (temp * temp) % p;
		} else {
			temp = power(a, k / 2, p);
			return (temp * temp * a) % p;
		}
	}
}