#include<bits/stdc++.h>
using namespace std;
long long int n,k;
long long int c[1000005];
struct n
{
	int x,y;
}s[1000005];
int main()
{
	memset(c,1,sizeof(c));
	c[0]=c[1]=0;
	for(int i=2;i*i<=1000000;i++)
	{
		if(!c[i])
		{
			continue;
		} 
		for(int k=i;k*i<=1000000;k++)
		{
			c[k*i]=0;
		}
	}
	cin>>n;
	for(int i=2;i<=n;i++)
	{
	if(c[i])
	{
		int t=0;
		for(int k=i;k<=n;k*=i)
		{
			t+=n/k;
		}
		if(t)
		{
			s[++k]={i,t};
		}		
	}		
	}
	for(int i=1;i<=k;i++)
	{
		cout<<s[i].x<<" "<<s[i].y<<'\n';
	}
	return 0;
}