1 #include 
         
           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 {_xx17     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 }