public static void main(String[] args) {
		int p = 1009;
		int q = 3643;
		
		int n = p*q;
		int phi = (p-1)*(q-1);
//		int phi = Euler.fi(p*q);
		BigInteger N = BigInteger.valueOf(n);
		
		System.out.println(phi);
		int[] ms = {116575, 142077, 346086, 462662, 469947, 1194903, 1522773, 1540990, 1548275, 1664850, 1664851, 1806927, 1868860, 2010936, 2010937, 2127512, 2134797, 2153014, 2480884, 3205840, 3213125, 3329701, 3533710, 3559212, 3675786};

		// disse deler alle
		// 346086, 1664850, 1664851, 2010936, 2010937, 3329701, 3675786 
		Set<Integer> unconcealable = new HashSet<Integer>(Arrays.asList(346086, 1664850, 1664851, 2010936, 2010937, 3329701, 3675786));
		
		long sum = 0;
		int count = 0;
		List<BigInteger> candidates = new ArrayList<BigInteger>();
		for (int e = 2; e < phi; e++) {
			if (e % 100000 == 0) {
				System.out.println(e + " / "+phi);
				System.out.println(sum);
			}
			if (Euler.gcd(e, phi) == 1) {
				BigInteger bigE = BigInteger.valueOf(e);
				int unconcealed = 0;
				for (int m: ms) {
					if (BigInteger.valueOf(m).modPow(bigE, N).intValue() == m) {
						unconcealed++;
					}
				}
				if (unconcealed == 7) {
					sum+=e;
					candidates.add(BigInteger.valueOf(e));
				}
				if (unconcealed < 7) {
					System.out.println("FUCK");
					System.exit(0);
				}
			}
		}
		
		
//		reccurse2(n, N, 2, unconcealable, candidates);
		reccurse(n, N, unconcealable, candidates);
		
		System.out.println(candidates.size());
		System.out.println(sum + " " + count);
		System.out.println(961081377984L);
	}