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

public class LegrendeSymbol2p {

	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++) {
				legrendeValue[(i * i) % p] = 1;
			}
			for (int i = 1; i < p; i++) {
				if (legrendeValue[i] == 0) {
					legrendeValue[i] = -1;
				}
			}
			int[] inverses = computeInverses(p);
			// This section is computing all possible values of t that satisfy
			// the constraints of Lemma 10.
			ArrayList<Integer> tArray = new ArrayList<Integer>();
			ArrayList<Integer> excludedSet = new ArrayList<Integer>();
			excludedSet.add(0);
			excludedSet.add(1);
			excludedSet.add(9);
			excludedSet.add(4);
			excludedSet.add(inverses[4]);
			excludedSet.add(inverses[9]);
			excludedSet.add(p - 1);
			for (int j = 1; j <= p - 1; j++) {
				int check1 = mod(1 - inverses[j], p);
				int check2 = mod(1 - j, p);
				if (legrendeValue[check1] == -1 && legrendeValue[check2] == -1 && !excludedSet.contains((Integer) j)) {
					tArray.add(j);
				}
			}
			// This part of the code is verifying that for some t from the above
			// set there exists a y such that
			// the condition in Lemma 13 are satisfied.
			boolean works = false;
			for (Integer t : tArray) {
				ArrayList<Integer> excludedSet2 = new ArrayList<Integer>();
				excludedSet2.add(0);
				excludedSet2.add(1);
				excludedSet2.add(2);
				excludedSet2.add(p - 1);
				excludedSet2.add(inverses[3]);
				excludedSet2.add(inverses[2]);
				excludedSet2.add(mod(2 * inverses[3], p));
				excludedSet2.add(mod(4 * inverses[t], p));
				excludedSet2.add(mod(4 * t, p));
				excludedSet2.add(mod(2 * inverses[mod(t + 2, p)], p));
				excludedSet2.add(inverses[mod(2 * t + 1, p)]);
				for (int y = 0; y < p; y++) {
					if (!excludedSet2.contains((Integer) y)) {
						int x1 = mod((1 - y), p);
						int x2 = mod(1 - 9 * y, p);
						int x3 = mod(1 - t * y, p);
						int x4 = mod((1 - 4 * t) ^ 2 * y ^ 2 - 2 * (4 * t + 1) * y + 1, p);
						if (legrendeValue[x1] == -1 && legrendeValue[x2] == 1 && legrendeValue[x3] == -1
								&& legrendeValue[x4] == -1) {
							works = true;
							System.out.println(p + " works with " + "t=" + t + ", y=" + y);
							break;
						}
					}
				}
				if (works) {
					break;
				}
			}
			if (!works) {
				System.out.println(p + " doesn't work");
			}
		}

	}

	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 = 15; i <= 10000; 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);
		}
		return output;
	}

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

	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;
		}
	}
}