1 #include <bits/stdc++.h> 2 #define INFB 0x3fffffffffffffff 3 #define INFS 0x3fffffff 4 #define _xx ios_base::sync_with_stdio(0);cin.tie(0); 5 using namespace std; 6 typedef long long ll; 7 bool isprime(int n) 8 { 9 if(n == 2) return true; 10 if(n == 1) return false; 11 for(int i = 2; i*i <= n; i++) 12 if(n%i == 0) return false; 13 return true; 14 } 15 int main() 16 {_xx 17 int n; 18 while(cin >> n) 19 { 20 if(n == 2) cout << 1 << endl; 21 else if(n%2 == 0) cout << 2 << endl; 22 else if(isprime(n)) cout << 1 << endl; 23 else if(isprime(n - 2)) cout << 2 << endl; 24 else cout << 3 << endl; 25 } 26 return 0; 27 }