import static java.math.BigInteger.probablePrime;
import static java.math.BigInteger.valueOf;

import java.io.*;
import java.util.Random;

public class TestsGen {
	static int[] primes;

	static {
		primes = new int[30];
		primes[0] = 2;
		for (int i = 1; i < primes.length; i++) {
			primes[i] = valueOf(primes[i - 1]).nextProbablePrime().intValue();
		}
	}
	static final Random rand = new Random(12762134123L);
	static final long MAXMEDIUM = 1000000000;
	static final long MAXN = 1000000000000L;

	static void printTest(long n, int k) {
		++curTest;
		File file = new File(curTest / 10 + "" + curTest % 10);
		while (file.exists()) {
			++curTest;
			file = new File(curTest / 10 + "" + curTest % 10);
		}
		try {
			System.err.println("Generating test #" + curTest);
			PrintWriter out = new PrintWriter(file);
			out.println(n + " " + k);
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	static int curTest = 0;

	public static void main(String[] args) {
		// ================================
		// First group of tests, for 50 points 
		// ================================
		printTest(120, 1);
		printTest(239, 5);
		printTest(2, 20);
		printTest(6, 4);
		printTest(8, 20);
		
		// LARGE PRIMES
		for (int i = 0; i < 5; i++) {
			int bits = rand.nextInt(6) + 23;
			int e = probablePrime(bits, rand).intValue();
			printTest(e, rand.nextInt(20) + 1);
		}
		
		// LARGE PRIMES multiplied by small numbers
		for (int i = 0; i < 5; i++) {
			int bits = rand.nextInt(6) + 20;
			int e = probablePrime(bits, rand).intValue();
			int maxp = 10;
			while (2 * e < MAXMEDIUM) {
				while ((long) primes[maxp] * e > MAXMEDIUM) {
					maxp--;
				}
				int p = rand.nextInt(maxp + 1);				
				e *= primes[p];
			}
			printTest(e, rand.nextInt(20) + 1);
		}
		
		// LARGE NUMBERS with many divisors
		long[] medium1 = ManyDivisorsContainingNumberGenerator.get(MAXMEDIUM,
				10);
		for (long e : medium1) {
			printTest(e, rand.nextInt(5) + 15);
		}
		
		// =========================
		// Second group tests, another 50 points
		// =========================
		
		long[] best = ManyDivisorsContainingNumberGenerator.get(MAXN, 10);
		if (best.length != 10) {
			throw new AssertionError();
		}
		for (long e : best) {
			printTest(e, rand.nextInt(5) + 96);
			printTest(e, rand.nextInt(5) + 86);
		}
		printTest(probablePrime(34 + rand.nextInt(5), rand).longValue(), 100);
		printTest(probablePrime(34 + rand.nextInt(5), rand).longValue(), 100);
		for (int i = 0; i < 3; i++) {
			int bits = rand.nextInt(6) + 30;
			long e = probablePrime(bits, rand).longValue();
			int maxp = 40;
			while (2 * e < MAXMEDIUM) {
				while ((long) primes[maxp] * e > MAXMEDIUM) {
					maxp--;
				}
				int p = rand.nextInt(maxp + 1);				
				e *= primes[p];
			}
			printTest(e, rand.nextInt(50) + 51);
		}
	}

	static class ManyDivisorsContainingNumberGenerator {

		static long[] get(long n, int count) {
			long[] ret = new long[count];
			int i = 0;
			int curPrimes = primes.length;
			for (; i < count / 2;) {
				go(0, 1, 1, OVERALLMAXPOWER, n, curPrimes);
				curPrimes = primesUsed - 1;
				ret[i++] = answer;
				if (divisorsGot < 600) {
					break;
				}
			}
			for (; i < count; i++) {
				go(0, 1, 1, OVERALLMAXPOWER, n, primes.length);
				ret[i] = n = answer;
				n--;
			}
			return ret;
		}

		static final int OVERALLMAXPOWER = 10;
		static int primesUsed;
		static long answer;
		static int divisorsGot;

		static void go(int x, long n, long div, int maxPow, long maxn,
				int maxPrime) {
			if (div > divisorsGot) {
				divisorsGot = (int) div;
				answer = n;
				primesUsed = x;
			}
			if (x == maxPrime || x == primes.length) {
				return;
			}
			long pow = 1;
			for (int i = 1; i <= maxPow; i++) {
				pow *= primes[x];
				if (pow * n > maxn) {
					break;
				}
				go(x + 1, n * pow, div * (i + 1), i, maxn, maxPrime);
			}
		}

	}

}
