using System;
using System.Numerics;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace a333595
{
    class a
    {
        static void Main(string[] args)
        {
            const int nOE = 50;
            List<int> primes = new List<int>(); // List of odd primes.
            BigInteger p = new BigInteger(0);
            primes.Add(3);
            for (int m = -1; m <= nOE - 2; m++)
            {
                if (m >= 0)
                {
                    int b = 2;
                    int currentStep = (m % 2) + 1;
                    while (true)
                    {
                        int test = b;
                        p = 2;
                        for (int j = 0; j <= m; j++)
                        {
                            while (test <= primes[j])
                            {
                                test *= b;
                            }
                            p = p * test + primes[j];
                        }
                        // Test the primality of p.
                        int certainty = p.GetCertainty();
                        if (BigIntegerExtensions.IsProbablePrime(p, certainty))
                        {
                            Console.WriteLine((m + 2).ToString("D").PadLeft(3, ' ') + " " + b.ToString("D"));
                            break;
                        }
                        else
                        {
                            b += currentStep;
                        }
                    }
                    GetNextPrime(m, primes);
                }
                else
                {
                    Console.WriteLine("  1 2");
                }
            }
        }

        static private void GetNextPrime(int m, List<int> primes)
        {
            primes.Add(primes[m] + 2);
            int k = 0;
            while (k == 0)
            {
                k = primes[m + 1];
                int j = 0;
                while (primes[j] * primes[j] <= primes[m + 1])
                {
                    k = primes[m + 1] % primes[j];
                    if (k > 0)
                        j++;
                    else
                        break;
                }
                if (k == 0)
                    primes[m + 1] += 2;
            }
        }
    }

    // Miller-Rabin primality test as an extension method on the BigInteger type.
    public static class BigIntegerExtensions
    {
        public static bool IsProbablePrime(this BigInteger source, int certainty)
        {
            if (source == 2 || source == 3)
                return true;
            if (source < 2 || source % 2 == 0)
                return false;

            BigInteger d = source - 1;
            int s = 0;

            while (d % 2 == 0)
            {
                d /= 2;
                s += 1;
            }

            // There is no built-in method for generating random BigInteger values.
            // Instead, random BigIntegers are constructed from randomly generated
            // byte arrays of the same length as the source.
            RandomNumberGenerator rng = RandomNumberGenerator.Create();
            byte[] bytes = new byte[source.ToByteArray().LongLength];
            BigInteger a;

            for (int i = 0; i < certainty; i++)
            {
                do
                {
                    // This may raise an exception in Mono 2.10.8 and earlier.
                    // http://bugzilla.xamarin.com/show_bug.cgi?id=2761
                    rng.GetBytes(bytes);
                    a = new BigInteger(bytes);
                }
                while (a < 2 || a >= source - 2);

                BigInteger x = BigInteger.ModPow(a, d, source);
                if (x == 1 || x == source - 1)
                    continue;

                for (int r = 1; r < s; r++)
                {
                    x = BigInteger.ModPow(x, 2, source);
                    if (x == 1)
                        return false;
                    if (x == source - 1)
                        break;
                }

                if (x != source - 1)
                    return false;
            }

            return true;
        }

        public static int GetCertainty(this BigInteger source)
        {
            int i = 0;
            BigInteger s = source;
            const int divisor = 2; // 2 would be the most conservative value.
            while (s > 0)
            {
                i++;
                s /= divisor;
            }
            return i;
        }
    }
}