#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1000010;
int prime[N], cnt, n;
bool sta[N];

void get_prime(int n)
{
    for(int i = 2; i <= n; i ++)//注意从2开始筛
    {
        if(sta[i]==false)//如果这个数没有被筛去，说明是质数
            prime[cnt ++] = i;
        for(int j = 0; prime[j] <= n/i; j ++)///注意这里是小于等于别漏掉
        {
            sta[prime[j]*i] = true;
            if(i % prime[j] == 0)
                break;
        }
    }

}

int main()
{
    scanf("%d", &n);
    get_prime(n);

    for(int i = 0; i < cnt; i ++)//遍历所有的质数
    {
        int s = 0, t = n;//注意这里不可以拿n直接计算，因为要遍历使用多次
        while(t)
        {
            s += t/prime[i];//累加计算出本质数prime[i]所有次方数
            t /= prime[i];
        }
        if(s)
            printf("%d %d\n", prime[i], s);
    }

    return 0;
}