#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stdint.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

void check_div (long long & res, long long d, long long lim)
{
    if (d >= lim)
    {
        res = min (res, d);
    }
}

long long min_next_div (long long n, long long lim)
{
    long long res = n;
    for (long long d = 2; d * d <= n; d++)
    {
        if (n % d == 0)
        {
            check_div (res, d, lim);
            check_div (res, n / d, lim);
        }
    }
    return res < n ? res : 0;
}

class Procrastination
{
public:
    long long findFinalAssignee (long long n)
    {
        long long cur = 2;
        int count = 0;
        while (cur <= n)
        {
            long long up = min_next_div (n, cur);
            long long down = min_next_div (n - 1, cur);
//          printf ("%I64d %I64d\n", up, down);
            count++;
            if (up && (!down || up <= down))
            {
                n++;
                cur = up + 1;
            }
            else if (down && (!up || down <= up))
            {
                n--;
                cur = down + 1;
            }
            else
            {
                break;
            }
        }
//      return n;
        return count;
    }
};

int main (void)
{
    Procrastination p;
    long long n;
    while (scanf (" %I64d", &n) > 0)
    {
        printf ("%I64d %I64d\n", n, p.findFinalAssignee (n));
        fflush (stdout);
    }
}