def isPrime(n):
if n % 2 == 0:
return n == 2
d = 3
while d * d <= n and n % d != 0:
d += 2
return d * d > n
x = int(input())
if isPrime(x):
print(1)
elif x % 2 == 0:
print(2)
elif isPrime(x - 2):
print(2)
else:
print(3)
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define boost ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define fill(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define pf push_front
//#define endl '\n'
#define fi first
#define se second
#define sz size()
#define mp make_pair
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
const ll INF = (ll)1e18 + 10;
const int N = 1e6;
const int M = N + 5;
const ld eps = 1e-12;
const ld pi = acos(-1);
const int dx[] = {0,0,-1,1,1,1,-1,-1},dy[] = {-1,1,0,0,1,-1,1,-1};
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
bool isprime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0){
return 0;
}
}
return 1;
}
void solve(){
int n;
cin>>n;
if(isprime(n)){
cout<<1;
}
else if(n%2==0||isprime(n-2)){
cout<<2;
}
else{
cout<<3;
}
}
int main() {
//boost;
srand(time(0));
//freopen("", "r", stdin);
//freopen("","w",stdout);
int ttt;
ttt=1;
while(ttt--){
solve();
}
return 0;
}1384A - Common Prefixes | 371A - K-Periodic Array |
1542A - Odd Set | 1567B - MEXor Mixup |
669A - Little Artem and Presents | 691B - s-palindrome |
851A - Arpa and a research in Mexican wave | 811A - Vladik and Courtesy |
1006B - Polycarp's Practice | 1422A - Fence |
21D - Traveling Graph | 1559B - Mocha and Red and Blue |
1579C - Ticks | 268B - Buttons |
898A - Rounding | 1372B - Omkar and Last Class of Math |
1025D - Recovering BST | 439A - Devu the Singer and Churu the Joker |
1323A - Even Subset Sum Problem | 1095A - Repeating Cipher |
630F - Selection of Personnel | 630K - Indivisibility |
20B - Equation | 600B - Queries about less or equal elements |
1015A - Points in Segments | 1593B - Make it Divisible by 25 |
680C - Bear and Prime 100 | 1300A - Non-zero |
1475E - Advertising Agency | 1345B - Card Constructions |