import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class TestGen {
	class Test {
		int n, m;

		public Test(int... a) {
			this.n = a[0];
			this.m = a[1];
		}

	}

	private int testCount = 0;

	private void write(Test t) {
		try {
			++testCount;
			System.err.println(testCount + " " + t.n + " " + t.m);
			String filename = testCount / 10 + "" + testCount % 10;
			PrintWriter out = new PrintWriter(filename);
			out.println(t.n + " " + t.m);
			out.flush();
			out.close();
		} catch (IOException ex) {
			throw new RuntimeException(ex);
		}
	}

	void myAssert(boolean b) {
		if (!b)
			throw new AssertionError();
	}

	static Random rand = new Random(1);
	int[][] HAND = {
			{
					12,
					18
			},
			{
					56,
					6
			},
			{
					2,
					1
			},
			{
					1,
					2
			},
			{
					1,
					1
			},
			{
					2,
					2
			},
			{
				2,
				3
		},
	};
	final int MAX = (int) 1e9;
	final int H1 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 37;
	final int P1 = BigInteger.valueOf((long) 1e9 - 100).nextProbablePrime().intValue();
	final int P2 = BigInteger.valueOf((long) 1e9 - 200).nextProbablePrime().intValue();

	public void run() throws IOException {
		for (int[] a : HAND) {
			write(new Test(a));
		}
		write(make2(H1, 10));
		write(make3(H1, MAX));
		write(new Test(H1, pow(2, MAX)));
		write(new Test(pow(2, MAX), 1));
		write(new Test(H1, pow(3, MAX)));
		write(new Test(H1, pow(37, MAX)));
		write(make2(P2, 10));
		write(make3(P2, MAX));
		write(new Test(P2, P1));
		write(new Test(P1, P2));
		write(new Test(H1, P2));
		write(new Test(P1, H1));
		write(new Test(pow(2, MAX / 3) * 3, pow(3, MAX / 2) * 2));
		write(new Test(BigInteger.probablePrime(29, rand).intValue(), BigInteger.probablePrime(29, rand).intValue()));

		for (int i = 0; i < 5; i++) {
			write(makeRandom(10));
			write(makeRandom(1000));
			write(makeRandom(10000000));
			write(make2(rand.nextInt(1000) + 2, 20));
			write(new Test(rand.nextInt(MAX) + 1, rand.nextInt(MAX) + 1));
			write(new Test(BigInteger.probablePrime(29, rand).intValue(), BigInteger.probablePrime(29, rand).intValue()));
		}
		write(new Test(pow(2, MAX / 3) * 3, pow(3, MAX / 2) * 2));
		write(new Test(pow(3, MAX / 2) * 2, pow(2, MAX / 3) * 3));
		write(new Test(pow(2, MAX / 3) * 3, pow(3, MAX)));
		write(new Test(pow(3, MAX / 2) * 2, pow(2, MAX)));
		write(new Test(pow(2, MAX / 15) * 3 * 5, pow(3, MAX)));
		write(new Test(pow(2, MAX / 15) * 3 * 5, pow(5, MAX)));
		write(new Test(MAX, MAX / 32 * 5 * 5));
		write(new Test(MAX, MAX / 25 * 16));
		write(new Test(MAX, MAX / 10));
		write(new Test(MAX, MAX));
	}

	int pow(int p, int max) {
		long r = 1;
		while (r * p <= max) {
			r *= p;
		}
		return (int) r;
	}

	int getAns(int n, int step) {
		ArrayList<Integer> p = primeDivisors(n);
		BigInteger r = BigInteger.valueOf(n);
		for (int i = 0; i < step || r.compareTo(BigInteger.valueOf((long) 1e9)) > 0; i++) {
			if (i < step && rand.nextBoolean()) {
				r = r.multiply(r);
			} else {
				int x = p.get(rand.nextInt(p.size()));
				if (r.mod(BigInteger.valueOf(x)).equals(BigInteger.ZERO) && r.compareTo(BigInteger.valueOf(x)) > 0) {
					r = r.divide(BigInteger.valueOf(x));
				}
			}
		}
		return r.intValue();
	}

	Test makeRandom(int max) {
		while (true) {
			Test t = new Test(rand.nextInt(max) + 1, rand.nextInt(max) + 1);
			if (solve(t.n, t.m) != null) {
				return t;
			}
		}
	}

	Test make2(int max, int step) {
		int n = max;
		Test t = new Test(n, getAns(n, step));
		return t;
	}

	Test make3(int n, int maxm) {
		ArrayList<Integer> p = primeDivisors(n);
		long m = 1;
		while (true) {
			int x = p.get(rand.nextInt(p.size()));
			if (m * x <= maxm) {
				m *= x;
			} else {
				break;
			}
		}
		Test t = new Test(n, (int) m);
		return t;
	}

	class Pair {
		int p, a;

		public Pair(int p, int a) {
			super();
			this.p = p;
			this.a = a;
		}

	}

	ArrayList<Pair> decomp(int n) {
		ArrayList<Pair> al = new ArrayList<Pair>();
		for (int i = 2; i * i <= n; i++) {
			if (n % i == 0) {
				int cnt = 0;
				while (n % i == 0) {
					cnt++;
					n /= i;
				}
				al.add(new Pair(i, cnt));
			}
		}
		if (n != 1) {
			al.add(new Pair(n, 1));
		}
		return al;
	}

	ArrayList<Integer> primeDivisors(int n) {
		ArrayList<Integer> al = new ArrayList<Integer>();
		for (int i = 2; i * i <= n; i++) {
			if (n % i == 0) {
				int cnt = 0;
				while (n % i == 0) {
					cnt++;
					n /= i;
				}
				al.add(i);
			}
		}
		if (n != 1) {
			al.add(n);
		}
		return al;
	}

	ArrayList<Integer> solve(int n, int m) {
		ArrayList<Pair> b = decomp(n);
		int[] a = new int[b.size()];
		for (int i = 0; i < a.length; i++) {
			while (m % b.get(i).p == 0) {
				m /= b.get(i).p;
				a[i]++;
			}
		}
		if (m != 1) {
			return null;
		}

		ArrayList<Integer> answer = new ArrayList<Integer>();
		while (true) {
			boolean need = false;
			for (int i = 0; i < a.length; i++) {
				if (a[i] > b.get(i).a) {
					need = true;
					break;
				}
			}
			if (!need)
				break;
			for (int i = 0; i < a.length; i++) {
				if (a[i] % 2 != 0) {
					a[i]++;
					answer.add(b.get(i).p);
				}
			}
			answer.add(0);
			for (int i = 0; i < a.length; i++) {
				a[i] /= 2;
			}
		}
		for (int i = 0; i < a.length; i++) {
			while (a[i] < b.get(i).a) {
				answer.add(b.get(i).p);
				a[i]++;
			}
		}
		Collections.reverse(answer);
		return answer;
	}

	public static void main(String[] args) throws IOException {
		new TestGen().run();
	}

}
