#include <iostream>
using namespace std;
bool p(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}
int main(){
int n;
cin>>n;
if(p(n)) cout<<1;
else if(n%2==0 || (n%2==1 && p(n-2))) cout<<2;
else cout<<3;
return 0;
}
CF上一遍过,洛谷上两遍都是Waiting!!!求大佬解答啊!!!难道UKE了?