#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
int n,num,vis[N],prime[N],ans;
void euler(){
    for(int i = 2;i <= n;++i){
        if(!vis[i]) vis[i] = prime[++num] = i;
        for(int j = 1;j <= num;++j){
            if(vis[i] < prime[j] || i * prime[j] > n) break;
            vis[i * prime[j]] = prime[j];
        }
    }
}
int main(){
    scanf("%d",&n);
    euler();
    for(int i = 1;i <= num;++i){
        printf("%d ",prime[i]);
        int x = n;
        for(;x;x /= prime[i])
            ans += x / prime[i];
        printf("%d\n",ans);
        ans = 0;
    }
}