rt，调了很久了，只过了 #1，#2。

#include<bits/stdc++.h>
using namespace std;
int f[1000000+5];int ans[1000000+5];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(int i=1;i<=1000000;i++) f[i]=i-1;
	for(int i=2;i<=1000000;i++)
	{
		int x=i;
		for(int j=2;j*j<=x;j++)
		{
			if(x%j==0)
			{
				f[i]=min(f[i],f[i-j]+1);
				while(x%j==0) x/=j;
			}
		}
		if(x>1)
		{
			f[i]=min(f[i],f[i-x]+1);
		}
	}
	int n;
	while(cin>>n)
	{
		ans[++ans[0]]=f[n];
	}
	for(long long i=1;i<=ans[0];i++) cout<<ans[i]<<"\n";
	return 0;
}