Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Mr. Funt now lives in a country with a very specific tax laws. The total income of mr.…

  1. User

    Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to n (n ≥ 2) burles and the amount of tax he has to pay is calculated as the maximum divisor of n (not equal to n, of course). For example, if n = 6 then Funt has to pay 3 burles, while for n = 25 he needs to pay 5 and if n = 2 he pays only 1 burle.

    As mr. Funt is a very opportunistic person he wants to cheat a bit. In particular, he wants to split the initial n in several parts n1 + n2 + ... + nk = n (here k is arbitrary, even k = 1 is allowed) and pay the taxes for each part separately. He can't make some part equal to 1 because it will reveal him. So, the condition ni ≥ 2 should hold for all i from 1 to k.

    Ostap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split n in parts. Input

    The first line of the input contains a single integer n (2 ≤ n ≤ 2·109) — the total year income of mr. Funt.

    Output

    Print one integer — minimum possible number of burles that mr. Funt has to pay as a tax.

    Examples

    Input

    4

    Output

    2

    Input

    27

    Output

    3

  2. DeepSeek Assistant

    We need to understand the problem: We have n ≥ 2. The tax on a number x (≥2) is defined as the maximum divisor of x that is less than x. That is essentially the largest proper divisor of x. For prime numbers, the largest proper divisor is 1? Wait: For prime numbers, the only divisors are 1 and itself. The maximum divisor not equal to n is 1. So tax(p) = 1 if p is prime. For composite numbers, the maximum proper divisor is n divided by its smallest prime factor. Actually, the largest proper divisor d < n satisfies d = n / p where p is the smallest prime factor of n. Because if n = a * b with a ≤ b, then the largest proper divisor is b = n / a, where a is the smallest divisor >1. So tax(n) = n / smallestPrimeFactor(n). So for prime, smallest prime factor is n, so tax = 1.

    Now we can split n into sum of parts each at least 2. For each part, we pay tax on that part. Total tax is sum of taxes on parts. We can choose any split (including k=1 meaning no split). We want to minimize total tax.

    We need to compute minimal possible total tax.

    Given n up to 2e9, we need an O(sqrt(n)) or even O(log n) solution.

    Let's analyze.

    Observation: For any part that is prime, tax=1, which is minimal for any individual number (since any composite yields tax at least >1). For composite, tax is at least 2 (since smallest prime factor at least 2, so tax = n / spf >= n/2? Actually minimum tax for a composite number occurs when its smallest prime factor is as large as possible? But note: tax = n / spf. So to minimize tax for a given n, we want spf to be as large as possible, i.e., we want n to be prime? Actually for prime tax=1 which is smallest. So primes are good. But we cannot use 1, and we cannot use part =1, but we can use prime parts to pay only 1 tax per part.

    However, we must sum parts to n. If we can split n into a sum of primes (all ≥2), then total tax = number of parts (since each prime part tax=1). But we also have to consider the possibility of using composite parts that might reduce total number of parts? Actually if we use composite parts, their tax might be >1, so total tax could be higher or lower depending on how many parts? For example, n=4. Options: k=1: tax(4) = max proper divisor of 4 = 2 (since 4/2=2). So total=2. Split into 2+2: each prime => tax each=1 => total=2. So both yield 2. Output 2.

    n=6: Option: no split: tax(6)=3 (since largest proper divisor 3). Split: 2+2+2 => total tax=3. 3+3 => each tax(3)=1, total=2. 2+4 => tax(2)=1, tax(4)=2 => total=3. So best is 2. So minimal total=2. Actually from sample: they gave 4->2, but 27->3. Let's test: n=27. No split: 27 smallest prime factor 3, tax=27/3=9 => total=9. Split: maybe 27 = 2+25: tax(2)=1, tax(25)=5 => total=6. 27=3+24: tax(3)=1, tax(24)=12? Actually largest proper divisor of 24 = 12 (since 24/2=12) => total=13. 27=5+22: 1+11=12? 11? Actually 22 tax = 11? 22 spf=2 => tax=11, total=12. 27=7+20: 1+10=11. 27=11+16: 1+8=9. 27=13+14: 1+7=8. 27=17+10: 1+5=6. 27=19+8:1+4=5. 27=23+4:1+2=3. So 23+4 yields total=3. But can we split into three parts? 3+11+13: taxes 1+1+1=3. So 3. Could we get 2? If we split into two primes: but 27 is odd, sum of two primes would be odd => one even and one odd. The only even prime is 2, so the other would be 25, but 25 is composite, tax=5, total=6. So two primes not possible (since 25 not prime). Could we split into one prime and one composite that yields tax 1? Composite tax can't be 1. So two parts total tax at least 1+2=3? Actually composite tax could be 2 if composite? Minimum composite tax is 2? For composite number x, spf at least 2, tax = x/spf >= x/2. For x≥4, tax >= 2? Actually for x=4, tax=2; for x=6, tax=3; for x=8, tax=4; for x=9, tax=3; So min tax for composite >=2. For x=2? But part must be >=2. If composite, then x>=4, so tax>=2. So two parts: if one is prime (tax1=1) and other composite tax2>=2 => total>=3. So minimal total=3, matches output.

    Hence, the problem reduces to: Given n, we can break it into sum of integers >=2. Each part with tax = 1 if prime, else tax = part/spf(part). Want minimize sum of taxes.

    Intuitively, using prime parts yields tax=1 per part. So the total tax is at least the number of parts. Because each part contributes at least 1. So the minimal total tax is at least the minimal number of parts we can achieve with each part being prime? But we could also use composite parts that yield tax less than the part's value, maybe less than 1 per part? No, tax is at least 1 for prime, and >1 for composite. So the minimal tax per part is 1. So the overall minimal possible total tax is at least the minimum number of parts we can split into (since each part contributes at least 1 tax). However, note that if we split into many parts, the number of parts might increase total tax. So we want to minimize tax, which is at least number of parts, but also each part might contribute more than 1 if composite. So ideally we want to use only prime parts (tax=1 each) and also want to minimize the number of parts (since each adds 1). But wait: If we use only prime parts, total tax = number of parts. So we would like to minimize the number of parts while having all parts prime? But is it always possible to represent n as sum of primes (except maybe when n is small)? This is related to Goldbach's conjecture: every even number ≥4 can be expressed as sum of two primes; every odd number ≥7 can be expressed as sum of three primes (weak Goldbach theorem, proven true for all odd numbers > 5? Actually, weak Goldbach's conjecture (now theorem) states that every odd number greater than 5 can be expressed as sum of three odd primes. But we need to handle n≥2. So for n≥2, what is minimal number of primes needed? For even n≥4: 2 primes (Goldbach). For odd n≥7: 3 primes (weak Goldbach). For n=3: sum of one prime? 3 is prime => one part => tax=1. For n=5: prime => tax=1. For n=2: prime => tax=1. For n=4: 2+2 or 3+1 (but 1 not allowed) so 2 primes? Actually 4 can be 2+2 => two primes, tax=2, but also 4 alone tax=2, so both same. So minimal tax for n≥2 would be? Let's check: if we can represent n as sum of k primes, then tax = k. So minimal possible tax would be the minimal k such that n can be expressed as sum of k integers ≥2 each prime. That's essentially the minimal number of primes needed to sum to n (with primes allowed to repeat). That's the "prime partition" minimal length. According to Goldbach, for even numbers >=4, min = 2 (or 1 if n itself is prime? For n prime, we can take k=1, tax=1, which is better than splitting into 2 primes? For n prime, tax=1 if we take it as single part. So we should always consider the possibility of not splitting. So the overall minimal tax is the minimum over all splits, not necessarily all primes. So we need to compare:

    • Option A: no split (k=1): tax = tax(n) = 1 if n is prime, else n/spf(n) (which could be large).
    • Option B: split into multiple parts, possibly achieving total tax = number of parts if all parts prime. And the minimal number of parts possible under prime-only splits.

    But we could also mix composites that might give total tax lower than number of parts? No, composites give tax >1, so mixing composites would increase tax beyond the count of parts. So optimal would either be:

    • Not split: tax(n)
    • Split into primes only, with some number of parts k (k>=2) such that sum of primes = n, yielding tax = k.
    • Possibly split with some parts being composite but achieving lower total tax than both of above? Could composite ever yield tax less than 1? No, so total tax >= k. So the minimal over all splits is at most min(tax(n), minimal k for prime partition). But also we might consider splits where some parts are composite but the total number of parts is lower? For example, n=9. tax(9)=9/3=3. Prime partition: 9=2+7 => tax=2 (2 primes) => total=2. Or 3+3+3 => tax=3. So best is 2. Could we do 4+5? tax(4)=2, tax(5)=1 => total=3. So best is 2. So prime partition with minimal k wins.

    But what about n=10? tax(10)=5 (since spf=2 -> tax=5). Prime partition: 10=5+5 => tax=2, or 3+7 =>2, or 2+2+2+2+2 =>5. So best=2. So far min(tax(n), minimal prime partition number) = minimal prime partition number except when n itself is prime (tax=1) which is better.

    But is there any case where splitting into composites yields total tax less than the minimal prime partition number? Let's think: Suppose we have a part that is composite but yields tax less than 1? impossible. So total tax = sum over parts of tax(part). Since each tax(part) ≥ 1, total tax ≥ number of parts. So to have total tax less than minimal prime partition number, we would need number of parts < minimal prime partition number but with some composites having tax exactly 1? No, only primes have tax=1. So if we have fewer parts than the minimal number of primes needed, at least one part must be composite, and that composite will have tax ≥2, so total tax ≥ (number of parts -1)*1 + 2 = number of parts +1 at minimum. If number of parts = k, then total tax ≥ k+? Actually worst case: if we have one composite and the rest primes, total tax = (k-1)1 + tax(composite) where tax(composite) ≥ 2 => total ≥ k+1. So total tax ≥ k+1 if at least one composite. So if minimal prime partition number is p, then for any split with k parts, if k ≤ p-1, then we would need at least one composite (since p is minimal number of primes that sum to n, we cannot have all primes if k<p). Then total tax ≥ k+1 ≥ p? Let's examine: Suppose p=2 (even number >=4 but not prime). Could we have k=1? That's no split, but n composite => tax(n) = n/spf which could be large, maybe >2? For n=4, tax(4)=2 which equals p=2? Actually p=2 because 4=2+2. So tax(4)=2 equals p. For n=6, tax(6)=3, p=2 (6=3+3) so p=2, tax(6)=3>2. So k=1 yields total tax 3, >2. k=2 with both primes yields total tax 2. So p works. For p=3 (odd composite not prime, e.g., 9). Could we have k=2? That would be two parts. Since minimal prime partition is 3, we cannot represent 9 as sum of two primes? Check: 9 = 2+7 (both primes) -> yes! Actually 9=2+7, so p=2 not 3. So 9 is odd but 2+7 works, so p=2. Wait Goldbach works for even numbers only; odd numbers can sometimes be sum of two primes if one is 2? Because sum of two odd primes is even; sum of 2 and an odd prime is odd. So any odd n = 2 + prime? That requires n-2 be prime. So if n-2 is prime, then p=2. Otherwise, p=3 (weak Goldbach). So for odd n that is not prime and n-2 not prime, p=3. Example: n=27. 27-2=25 not prime, so p=3. So we can have k=2? Could we represent 27 as sum of two composites or one prime one composite? But that would have tax =1+tax(composite). Minimum tax(composite) for part at least 2? For composite part of size at least 4, tax≥2, so total≥3. For part=2? But 2 is prime. So if we try k=2, we would have either both primes (not possible since n-2 not prime) or one prime one composite. Then total tax ≥ 1+2=3. So total tax could be exactly 3 if we find a composite part with tax=2 (i.e., part=4? 4 tax=2). So can we have 27 = 23+4? Yes, 23 prime, 4 composite with tax=2 => total=3. That's same as p=3 (3 primes each tax=1). So k=2 gave total=3, which equals p=3. So total tax maybe can be p even with k<p? Let's analyze: For p=3, can we have k=2 giving total tax = 3? Because if we have one composite with tax=2 and one prime with tax=1, total=3. That equals p. So it's not larger than p. But could it be less than p? If we could have composite with tax=1? impossible. So total tax >= k+1 when exactly one composite? But if we have two composites, could total tax be lower? For k=2, both composites: each tax≥2, so total≥4 >3. So only mix of one prime and one composite yields total ≥ 3 if the composite tax can be exactly 2. But is it always possible to find such a composite part (with tax=2) such that the other part (n - part) is prime? For n with p=3, we need n = prime + composite, where composite has tax=2. Which composites have tax=2? tax(x)=2 => x/spf(x)=2 => x = 2 * spf(x) and spf(x) is smallest prime factor. If spf(x)=2, then x=4. Actually if spf(x)=2, then tax(x)=x/2. For tax(x)=2, we need x=4. If spf(x)=p>2, then tax(x)=x/p. For it to be 2, x=2p, but then spf(2p)=2 (since even), so spf=2, tax = (2p)/2 = p, not 2 unless p=2. So the only composite with tax=2 is 4? Let's test: x=9, spf=3, tax=3; x=25, tax=5; x=6, tax=3; x=8, tax=4; x=10, tax=5; x=12, tax=6; So only x=4 yields tax=2? What about x=2? But 2 is prime. So indeed only composite with tax=2 is 4. Could there be any other? x= (some prime squared) yields tax = x/p = p^2/p = p, so >2 for p>2. x=2p with p odd => spf=2, tax = (2p)/2 = p ≥3. So only 4 gives tax=2. Also note x=1? not allowed. So the only way to have a composite part with tax=2 is to have part=4.

    Thus, for odd n with p=3, a split into two parts (prime + 4) gives total tax = 1+2=3, same as p. But is it always possible that n-4 is prime? That would require n-4 prime. For n=27, 23 prime yes. For n=21: 21-4=17 prime, yes. For n=25: 25-4=21 not prime; but 25 itself is composite, tax(25)=5. p? 25 is odd composite, 25-2=23 prime? 23 prime => p=2? Actually 25=2+23, both primes, so p=2. So minimal tax is 2. So for p=3 we need n such that n-2 not prime (so p=3) but also n-4 could be prime? Possibly not always. For example, n=9? But 9-2=7 prime, so p=2. n=15: 15-2=13 prime, so p=2. n=27 works. n=33: 33-2=31 prime -> p=2. n=35: 35-2=33 composite, so p=3. 35-4=31 prime -> works, total=3. n=45: 45-2=43 prime -> p=2. n=49: 49-2=47 prime -> p=2. n=51: 51-2=49 composite, so p=3. 51-4=47 prime -> works. n=55: 55-2=53 prime -> p=2. n=57: 57-2=55 composite, p=3. 57-4=53 prime -> works. n=75: 75-2=73 prime -> p=2. Seems many odd composites where n-2 is composite but n-4 prime? Might hold? Not always: Consider n=11 (prime) p=1. n=17 prime p=1. For composite odd: n=81? 81-2=79 prime? 79 is prime, so p=2. n=87: 87-2=85 composite, p=3? 87-4=83 prime? 83 prime -> works. n=93: 93-2=91 composite (713), so p=3; 93-4=89 prime? 89 prime -> works. n=95: 95-2=93 composite, p=3; 95-4=91 composite (713) not prime. So 95: n=95, p=3, but 95-4=91 not prime. Could we have another composite with tax=2? Only 4. So split into prime + 4 not possible. Could we do prime + composite with tax= something less than 2? No. Could we do prime + composite with tax=2? Only 4. So if n-4 not prime, then two-part split would need either two primes (impossible) or one prime and composite with tax>2 => total >=1+3=4, which is >3. Or both composites: each tax≥? at least one maybe 4? Actually composite tax can be 3 for 9? But 9 tax=3; 6 tax=3; 8 tax=4; 10 tax=5; 12 tax=6; 14 tax=7; 15 tax=5? Actually 15 spf=3, tax=5. So minimum composite tax for numbers >=6 is 3 (for 6? 6 tax=3, for 9 tax=3, for 4 tax=2, but 4 is special). So for parts ≥5, composite tax >=? For 6 tax=3, for 8 tax=4, for 9 tax=3, for 10 tax=5, for 12 tax=6, for 14 tax=7, for 15 tax=5, for 16 tax=8, for 18 tax=9, for 20 tax=10, for 21 tax=7? Actually 21 spf=3 tax=7, for 22 tax=11, for 24 tax=12, for 25 tax=5, for 26 tax=13, for 27 tax=9, for 28 tax=14, for 30 tax=15, etc. So the smallest composite tax beyond 4 is 3 (for 6,9). But note 6 and 9 are ≥6 and tax=3. However, can we use 6 or 9 to get total tax =? For two-part split, we need n - part to be prime. So if we try part = 6 (tax=3), we need n-6 prime. That would give total tax = 1+3=4, which is >3. Part=9 tax=3 gives n-9 prime => total=4. So total tax 4 >3. Could we use part = 8 tax=4 => total≥5. So minimal total for two parts would be 4 if we can get prime + composite with tax=3. But that is still larger than p=3. So for n with p=3 and n-4 not prime, the best might be to use three primes (p=3) giving total=3. Or maybe split into more parts but still total tax = number of parts if all primes, but if we need 3 primes, that's total=3. Could we do 4 parts? That would be total≥4, worse. So minimal total = 3.

    Thus, for odd composite where p=3, the answer appears to be 3, provided we can achieve it via three primes (always by weak Goldbach, for odd >=7, can be expressed as sum of three primes, but note that we require each part >=2 and prime, and primes can be 2 as well; weak Goldbach says every odd number greater than 5 can be expressed as sum of three odd primes. Actually includes 2? Sum of three primes: if one of them is 2, then the other two sum to odd-2 which is odd, so they'd be odd primes. That's allowed. So for any odd n >= 7, we can represent as sum of three primes (since weak Goldbach holds for all odd n > 5, I think it's proven for all odd n > 5. The problem constraints n up to 2e9, so it's fine). For n=3,5 they are prime themselves, p=1, answer=1. So indeed, for odd composite where n-2 is not prime, answer = 3.

    Now what about even numbers? For even n ≥ 4. Cases:

    • If n is prime? Even prime only 2. n=2, answer = 1 (tax(2)=1). For n even >2, n is composite (since even >2 has factor 2). So tax(n) = n/2. That could be large.

    • Minimal prime partition: Goldbach says any even n ≥ 4 can be expressed as sum of two primes. So p can be 2, but sometimes n itself might be prime? not for even >2. So p=2. So we can have total tax = 2 using two primes. However, is it always optimal? Could there be a better split using composites that yields total tax = 1? That would require k=1 part prime (n itself prime) but n even >2 not prime. So can't have tax=1. Could we have split into k=2 parts where one part is prime and the other is composite with tax=1? No composite tax=1 impossible. So total tax must be at least 2. So answer for even n ≥ 4 is at least 2. But is there any even n where we can achieve total tax = 1? No. So answer is at most 2 by using two primes. So for even n ≥ 4, answer = 2? But careful: There is also the possibility of not splitting, which could yield tax = n/2. That is >=2 for n≥4, but often larger. So answer should be 2, unless there is some even n where we cannot split into two primes? But Goldbach's conjecture states every even number > 2 can be expressed as sum of two primes. This is a conjecture, but it's widely believed true and has been verified up to very large numbers (>> 2e9). In programming competitions, they often treat Goldbach as true for given constraints? Actually, this is a problem from Codeforces (I recall problem 454A? No maybe 302A? I'm not sure). The typical solution for this problem is: if n is prime, answer = 1; else if n is even, answer = 2; else (n is odd composite) check if n-2 is prime; if yes answer = 2; else answer = 3. I think that's the standard solution for Codeforces 735A? Not sure. Wait I recall a problem "Taxes" from Codeforces #735? Actually there is a problem "C. Taxes" from Codeforces Round #? I think it's Codeforces Round # 735 (Div. 2) Problem C? Let's check memory: There is a problem "C. Taxes" where solution is exactly that: If n is prime -> 1; else if n is even -> 2; else if n-2 is prime -> 2; else -> 3. That matches our analysis. However, we must also consider special cases like n=2 (prime ->1), n=4 (even composite, answer=2). n=6 (even composite, answer=2? But earlier we found answer for 6 was 2 (3+3). Yes. n=8 even -> answer=2 (3+5). n=9 (odd composite, 9-2=7 prime, answer=2). n=15? 15-2=13 prime -> answer=2 (2+13 gives tax=1+1=2). Check: 15 split into 2 and 13, both primes, total=2. Indeed optimal. n=21: 21-2=19 prime -> answer=2. n=25: 25-2=23 prime -> answer=2. So many odd composites also give answer 2. Only those where n-2 not prime (odd composite) give answer 3. Example: 27 as sample gave 3. So answer pattern:

    • n=2 -> 1.

    • n prime -> 1.

    • else if n even -> 2.

    • else (odd composite) if n-2 is prime -> 2 else -> 3.

    But we need to consider n=1? Not allowed (n>=2). So that's it.

    But wait: There's nuance about splitting into two parts with composite part 4 giving total tax 2? Actually if we use composite 4, tax=2, and prime part tax=1, total=3, not 2. So that's only used when n-2 not prime but n-4 prime? That gave 3, same as three primes. So not better.

    But could we ever achieve total tax = 2 for odd composite n where n-2 is not prime? If we could find a composite part with tax=1? impossible. So min total tax = 2 only possible via two primes, i.e., n = p + q with p, q primes (both ≥2). Since n is odd, one must be 2, the other n-2 must be prime. So condition exactly n-2 prime. So that matches.

    Thus, solution reduces to checking primality and parity.

    But we must be careful about the case n=2? prime ->1. n=3 prime ->1. n=4 even ->2. n=5 prime ->1. n=6 even ->2. n=7 prime ->1. n=8 even ->2. n=9: odd composite, 9-2=7 prime ->2. n=10 even ->2. n=11 prime ->1. n=12 even ->2. n=13 prime ->1. n=14 even ->2. n=15: odd, 15-2=13 prime ->2. n=16 even ->2. n=17 prime ->1. n=18 even ->2. n=19 prime ->1. n=20 even ->2. n=21 odd, 21-2=19 prime ->2. n=22 even ->2. n=23 prime ->1. n=24 even ->2. n=25 odd, 25-2=23 prime ->2. n=26 even ->2. n=27 odd, 27-2=25 not prime ->3. etc.

    Check n=27 we know answer=3. n=33 odd, 33-2=31 prime ->2. n=35 odd, 35-2=33 composite ->3? But 35-2=33 composite, so answer=3? Let's test manually: 35 = 2+33 (tax 1+? 33 tax=11? Actually 33 spf=3 => tax=11, total=12). 35=3+32 (1+16=17). 35=4+31 (2+1=3) => 4 composite tax=2, 31 prime tax=1 => total=3. So 3 is possible. Can we get 2? Need both primes: 2+33 no, 33 not prime; other combos: 13+22? 22 composite tax 11; 19+16? 16 tax=8; etc. So 3 is minimal. So answer=3 matches.

    Now, what about n=2? prime->1, good.

    Edge case: n=2*prime? That's even, answer=2. So seems solid.

    But is there any case where n is even but we cannot split into two primes? According to Goldbach's conjecture, it is believed but not proven for all numbers, but for n up to 2e9, we could check if n is even >2 and we assume it's always possible? However, we are solving a programming problem, so they expect a solution that doesn't rely on unproven conjecture? Actually the problem is from Codeforces and the official solution uses the conjecture. Usually in programming contests, they treat Goldbach as true for the given constraints because it's been verified up to 4e18 or something, and the input n ≤ 2e9, which is within the range it's known to be true? Actually Goldbach's conjecture has been verified up to at least 4×10^18, so 2e9 is fine. So we can safely use it. But to be rigorous, we could implement a primality test and then derive answer.

    Thus, the solution:

    if isPrime(n): print(1) elif n % 2 == 0: print(2) else: # n odd composite if isPrime(n-2): print(2) else: print(3)

    But careful: When n is even, could the answer ever be 1? No, because n even >2 is composite, so tax(n) >=2. Could we get total tax =1 by splitting? Splitting would yield at least two parts (since parts >=2, sum n>2). If we split into two parts, each at least 2, then sum of two numbers each ≥2 gives n≥4. So for n=2, we handled separately. So answer for even n≥4 is at least 2, and we can achieve 2 via two primes. So yes.

    But what about n=4? even, we claim answer=2, works. n=6: answer=2, works.

    Now, there might be a nuance: Could the answer be 0? No.

    Now, what about n=9? odd composite, n-2=7 prime, answer=2. Indeed 2+7 works.

    Now, is there any case where n is odd composite, n-2 not prime, but we could still achieve total tax=2 via some other split not consisting of two primes? For instance, if one part is prime and the other part is composite with tax=1? impossible. So no.

    Thus, the answer is as described.

    But let's double-check: The tax function for prime is 1. However, what about the part equal to 1? Not allowed. So we cannot use 1.

    Thus, the solution is simple.

    But we need to implement primality test for n up to 2e9. That's easy: trial division up to sqrt(n) which is about 44721. That's fine. Use deterministic Miller-Rabin? Not needed, sqrt(2e9) ~44721, so we can check divisibility by numbers up to sqrt(n). That's O(sqrt(n)) which is about 44721 operations, which is fine in most languages. However, we need to test primality for n and maybe n-2. n-2 also up to 2e9. So at most two primality tests. So straightforward trial division up to sqrt is okay (44721 per test). But careful: We need to check primality for n up to 2e9, sqrt is about 44721, that's okay.

    Alternatively, we can use a faster check: check divisibility by primes up to sqrt, but generating primes via sieve up to 44721 (about 4600 primes) is also easy. But trial division by all odd numbers up to sqrt is acceptable: 44721/2 ~ 22360 iterations, times 2 = ~44720 operations, which is trivial.

    But we also need to handle n=2 and n=3 etc.

    Edge case: n=2 -> prime, answer 1. n=3 -> prime, answer 1. n=4 -> even, answer 2. n=5 -> prime, answer 1. n=6 -> even, answer 2. n=7 -> prime, answer 1. n=8 -> even, answer 2. n=9 -> odd composite, n-2=7 prime -> answer 2. n=10 -> even, answer 2.

    Now, what about n=1? not allowed.

    Thus, implementation.

    But wait: Could there be a case where n is even but we could get total tax = 1 by using a single prime part? No, because n is even >2, not prime. So no.

    So algorithm:

    Read n.

    If n is 2: print 1. But we will have isPrime function handle.

    But careful: In some definitions, 2 is prime, so isPrime(2)=true, answer=1.

    Now, what about n being a prime power? Already covered.

    Thus, answer.

    But let's verify a few more examples:

    n=12: even -> 2. Indeed 5+7 -> both primes => tax=2.

    n=14: 7+7 ->2.

    n=16: 13+3 ->2.

    n=18: 11+7 ->2.

    n=20: 13+7 ->2.

    n=22: 11+11 ->2.

    n=24: 11+13 ->2.

    n=26: 13+13 ->2.

    n=28: 11+17 ->2.

    All good.

    Odd composite where n-2 prime: as above.

    Now, odd composite where n-2 not prime: e.g., 27, 35, 45? Check 45: 45-2=43 prime -> actually 43 prime, so answer=2. So 45 is 2+43 ->2. 45 also 2+43 works. So not all odd composites give 3. Indeed many give 2.

    So the only odd composites that give 3 are those where n-2 is composite (i.e., n-2 is not prime). In other words, n is odd and not prime, and also n-2 is not prime. For odd n, note that if n is prime, we already answer 1. So for odd n that are not prime, check if n-2 is prime. If yes, answer=2; else answer=3.

    Now, could there be a scenario where n is odd, n-2 not prime, but we can still get total tax=2 by using one composite part that is 4? That gives total 3, not 2. So no.

    But what about splitting into 3 parts but total tax = 2? That would require at least two parts having tax 0? No.

    So answer 3 is minimal.

    Now, what about n=2? prime, answer 1.

    n=3, answer 1.

    n=2 is prime.

    Now, are there any corner cases like n=4? we said answer 2, but could we get 1? No.

    Thus solution.

    But is it always possible to represent odd n>=9 as sum of three primes? For n=9, it's 2+2+5? Actually 2+2+5=9, primes (2,2,5) all allowed (parts can be equal). So yes. For n=11? but 11 is prime, answer 1. For n=13 prime, answer 1. For n=15, 15 is composite, but n-2=13 prime, answer 2. So we don't need three. For n=17 prime, answer 1. For n=19 prime, answer 1. For n=21 composite, 21-2=19 prime => 2. For n=23 prime =>1. For n=25 composite, 25-2=23 prime =>2. For n=27 composite, 27-2=25 composite => need three primes, e.g., 3+11+13=27, all primes =>3. So fine.

    Now, could there be odd n=1? no.

    Now, about the primality test: We need to be efficient for up to 2e9. Write a function isPrime(x) that returns true if x is prime. Handle x < 2: false. For even numbers, we can quickly check. But given our logic, we call isPrime for n and maybe n-2 only when n is odd and >2 (since if n even, we don't call isPrime(n) unless we check earlier). Actually we check: if isPrime(n) -> 1. So for even n, isPrime(n) will be false (except 2). So we can skip checking n-2 for even n. So we only check n-2 for odd n not prime.

    Thus, we can implement:

    if n == 2: print 1 (but isPrime handles) else if n%2==0: print 2 else: if isPrime(n): print 1 else if isPrime(n-2): print 2 else: print 3

    But careful: If n is odd and prime, isPrime(n) true, we print 1 and done. For odd composite, we check n-2 primality.

    Now, check n=9: odd composite, n-2=7 prime -> print 2, correct.

    n=15: odd composite, n-2=13 prime -> 2.

    n=27: odd composite, n-2=25 composite -> print 3.

    n=2: even but prime, our code: if n%2==0: print 2 would incorrectly print 2 for n=2. So we need to treat n=2 as a special case, or structure the conditions differently: first check primality, if prime => 1 (this covers n=2,3,5,...). Then for non-prime, check even => 2, else (odd composite) => check n-2 prime? => 2 else 3. That works.

    So:

    if isPrime(n): print(1) else: if n % 2 == 0: print(2) else: if isPrime(n-2): print(2) else: print(3)

    That's correct: n even non-prime => 2; n odd non-prime => if n-2 prime => 2 else 3.

    But wait: For n=4, isPrime(4)=false, n%2==0 true => print 2, correct. For n=6, same.

    For n=9: isPrime(9) false, n%2==1, check isPrime(9-2=7) true => print 2.

    For n=27: isPrime false, odd, isPrime(25) false => print 3.

    For n=2: isPrime(2) true => print 1.

    Thus, correct.

    Now, we must ensure isPrime works for n up to 2e9. We'll implement a deterministic function checking divisibility by 2 and then odd i up to sqrt. sqrt(2e9) ~44721, which is fine.

    But careful: n could be 1? No.

    Edge: n-2 could be 1? For n=3, we don't go to else branch because isPrime(3)=true. For n=4? even. For n=5 prime. For n=7 prime. For n=9: n-2=7 ok. For n=2? prime. So n-2 is at least 0? For n=3 not considered. For n=1 not allowed. So safe.

    Now, we must also consider the possibility that the answer could be 0? No.

    So final solution: implement isPrime(x) for x up to 2e9.

    Potential pitfalls: When x is 1, isPrime false. But we never call with x=1? Possibly n-2 could be 1 if n=3, but we don't call because n is prime. So safe.

    Now, is there any scenario where n is odd composite but n-2 is prime but splitting into two primes (2 and n-2) yields a part =2, which is allowed (since part must be >=2). Yes, 2 is allowed. So good.

    Thus, answer is as above.

    Now, double-check for n=2: print 1.

    Now, but what about n=3? print 1.

    Now, let's test some larger numbers:

    n=1e9+7? Actually 1000000007 is prime, answer 1. But we need to test primality quickly; our sqrt loop up to 31623 (since sqrt(1e9)~31623) Actually sqrt(2e9) ~44721, so for 1e9+7, sqrt ~31623, iteration over odd numbers up to 31623 is about 15811, fine.

    But we should consider that worst-case n around 2e9, sqrt ~44721, odd numbers up to 44721 = about 22360 divisions, plus divisibility by 2 check, that's fine.

    Alternatively, we can optimize by checking divisibility by primes only, but not necessary.

    Thus, solution is straightforward.

    But wait: There is a nuance: The tax on a part that is composite might be less than the number of prime parts? Actually we determined minimal total tax is either 1,2, or 3. But is it possible that for some n, the minimal total tax is >3? Let's think: For n even, we can always get 2. For odd composite where n-2 is prime, we can get 2. For odd composite where n-2 not prime, we can get 3. So answer never exceeds 3. For n odd composite and n-2 not prime, can we always get 3? Yes, by weak Goldbach, we can represent any odd number >= 7 as sum of three primes. For n=9, we have 2+2+5, works. For n=15, n-2 prime, so we don't need 3 but we could also use 3 primes but answer 2 is better. For n=27, 3+11+13 works. For n=35, 2+2+31? Actually 2+2+31=35? 2+2+31=35, yes, primes. So always possible.

    But is there any odd composite where n-2 not prime and also n cannot be expressed as sum of three primes? According to weak Goldbach theorem (proved by Helfgott for all odd n > 5), it is true for all odd n >= 7. So for n up to 2e9, it's definitely true. So answer 3 is achievable.

    Thus, answer is at most 3.

    Now, could answer be 0? No.

    Now, final check: Did we consider n=2* something? Already.

    Thus, problem solved.

    Now, we must produce code accordingly.

    But there is an alternative scenario: Could there be a split that yields total tax = 2 for odd composite when n-2 not prime by using a composite part with tax=1? No.

    So done.

    Now, implement isPrime efficiently.

    Pseudo:

    def isPrime(x): if x < 2: return False if x % 2 == 0: return x == 2 i = 3 while i*i <= x: if x % i == 0: return False i += 2 return True

    But careful: For x up to 2e9, i*i may overflow in some languages? In Python, fine. In C++, use long long.

    Thus, final answer.

    But wait: There's a twist: The tax for a part is defined as the maximum divisor of n not equal to n. That is indeed the largest proper divisor. For prime numbers, that's 1. For composite, as described. So our reasoning stands.

    Now, confirm with given examples:

    Input 4 -> Output 2. Our code: isPrime(4) false, even => 2.

    Input 27 -> Output 3. isPrime false, odd, isPrime(25) false => 3.

    Matches.

    Edge: Input 2 -> Output 1. isPrime true => 1.

    So fine.

    Now, also we should test n=1? Not allowed.

    Now, the problem statement says n>=2.

    Thus, solution done.

    But let's also think about a scenario: n = 3? output 1.

    Now, could there be any scenario where n is even but splitting into two primes is not possible? For n=2, it's prime, we answer 1. For n=4, 2+2 works. For n=6, 3+3 works. For n=8, 3+5 works. For n=10, 5+5 works. For n=12, 5+7 works. For n=14, 7+7 works. For n=16, 13+3 works. For n=18, 11+7 works. For n=20, 13+7 works. For n=22, 11+11 works. For n=24, 11+13 works. For n=26, 13+13 works. For n=28, 11+17 works. For n=30, 13+17? 13+17=30, yes. It's widely believed Goldbach holds for all even numbers, and it's known to hold up to 4e18, so for 2e9 it's definitely true. So safe.

    Thus, final solution.

    But maybe there is an even n where the optimal is not 2 but 1? No.

    Now, there is one more nuance: The tax on a part is defined as the maximum divisor less than the number. For 4, that's 2. So that matches.

    Now, one more edge: What about n=2? tax=1. So answer 1.

    Now, implement.

    But we should also consider if there is a possibility to achieve total tax = 0? No.

    Thus, final answer.

    Now, produce final code in Python.

    Plan:

    • Read integer n.

    • Define function is_prime(x): if x < 2: return False if x % 2 == 0: return x == 2 i = 3 while i * i <= x: if x % i == 0: return False i += 2 return True

    • Then:

    if is_prime(n): print(1) else: if n % 2 == 0: print(2) else: if is_prime(n-2): print(2) else: print(3)

    That's it.

    But wait: For n=4, is_prime(4) false, even => 2.

    Now, check n=9: is_prime false, odd, is_prime(7) true => 2.

    Now, check n=25: is_prime false, odd, is_prime(23) true => 2.

    Now, check n=27: is_prime false, odd, is_prime(25) false => 3.

    Works.

    Now, think about n=2e9 (2000000000). That's even, is_prime false, so answer 2. That seems plausible.

    Now, time complexity: O(sqrt(n)) which is fine.

    Now, let's double-check the primality test for large numbers: We need to ensure ii doesn't overflow in Python? Python handles big ints, but it's fine. However, for speed, we can set an upper bound int(math.sqrt(x)) and iterate only up to that. But while ii <= x is okay, as Python will compute big ints but it's okay. Alternatively, use integer sqrt to avoid repeated multiplication? But 44721 multiplication is fine.

    Better: limit = int(x**0.5) + 1 and loop. But careful with floating errors? x up to 2e9, sqrt(2e9) ≈ 44721.36, square of 44722 is 2,000,0?? Actually 44722^2 = (4472244722) = 2,000,0? Let's compute: 44722^2 = (44720^2 + 2447202 + 2^2) ... but it's about 2,000, something; but it's >2e9? 44721^2 =? 44721^2 = (44700^2=1998090000) + extra; I think 44721^2 = 199,? Let's calculate: 44721^2 = (4472144721). 44720^2 = 4472044720 = 1,999,? Actually compute: 44724472? Let's do: 44721^2 = (45000-279)^2 = 2025000000 - 245000279 + 279^2 = 2025000000 - 25110000 + 77841 = 199,? Actually 2025000000-25110000=1999890000, +77841=1999967841. That's less than 2e9=2000000000. 44722^2 = (44721+1)^2 = 1999967841 + 244721 +1 = 1999967841+89442+1=2000057284 > 2e9. So sqrt(2e9) ≈44721.36, so limit 44721 works. So using ii <= x is fine.

    Now, consider n=2e9-1? That's odd, maybe composite. We'll test is_prime? Could be prime? Unlikely, but we need to handle.

    Now, implementation note: The is_prime function should be optimized a bit: check divisibility by 2, then by odd numbers starting from 3. Also check for 3,5,7? Not needed.

    Thus, final answer.

    But wait, there is another subtlety: The problem statement says "split the initial n in several parts n1 + n2 + ... + nk = n (here k is arbitrary, even k = 1 is allowed) and pay the taxes for each part separately. He can't make some part equal to 1 because it will reveal him. So, the condition ni ≥ 2 should hold for all i from 1 to k." So any part must be at least 2. That's what we used. So primes like 2 are allowed.

    Now, question: Could we have a part that is 0? No.

    Thus, all good.

    Now, produce final answer in Python.

    We need to handle input reading. Usually Codeforces uses sys.stdin.

    Now, final code:

    import sys import math

    def is_prime(x): if x < 2: return False if x == 2 or x == 3: return True if x % 2 == 0: return False i = 3 while i * i <= x: if x % i == 0: return False i += 2 return True

    def solve(): n = int(sys.stdin.readline().strip()) if is_prime(n): print(1) else: if n % 2 == 0: print(2) else: if is_prime(n-2): print(2) else: print(3)

    if name == "main": solve()

    Now, test with examples:

    Input: 4 -> is_prime false, even -> 2. Output 2.

    Input: 27 -> is_prime false, odd, is_prime(25) false -> 3.

    Works.

    Now, we should also test with n=2 -> is_prime true -> 1.

    n=3 -> 1.

    n=5 -> 1.

    n=9 -> 2.

    n=15 -> 2.

    n=21 -> 2.

    n=25 -> 2.

    n=27 -> 3.

    n=35 -> 3.

    n=45 -> 2? Actually 45-2=43 prime, so 2.

    n=49 -> 49-2=47 prime =>2? Check 49 is composite, 7^2, tax(49)=7, but split into 2+47 yields tax 1+1=2, yes.

    n=51 -> 51-2=49 composite =>3? Check 51-2=49 not prime, so 3. Indeed 2+49 gives tax 1+? 49 tax=7 -> total=8; 4+47 -> 2+1=3; So 3.

    All good.

    Now, but is there any case where n is odd composite and n-2 is prime but the split 2+(n-2) is valid only if n-2 >=2, which it is because n>=5. So fine.

    Thus, answer.

    One more nuance: For n=2e9+? n max 2e9, n-2 may be close to 2e9, still fine.

    Now, finalize.

    But wait: Could there be a scenario where we can achieve total tax = 2 for odd composite with n-2 not prime using a composite part that is not 4 but with tax=1? No.

    Thus, correct.

    Now, I recall a Codeforces problem "C. Taxes" (maybe from Round 735) where the solution is exactly as above. So this is correct.

    Now, potential pitfalls: The primality test might be too slow if we just loop up to sqrt for each test. But n up to 2e9, sqrt=44721, so at most 44721/2 = 22360 divisions per test, and we may do two tests (n and n-2). That's about 44720 divisions, which is fine in Python. Even in worst-case, we can precompute primes up to 44721 using sieve to reduce divisions to about 4600 per test. But not necessary.

    But note: For n up to 2e9, we might be required to handle many test cases? The problem has only one input. So it's fine.

    Thus, final answer.

    Now, we can also consider alternative approach: The answer is:

    • 1 if n is prime
    • 2 if n is even or (n-2) is prime
    • 3 otherwise

    This can be written succinctly.

    Now, one more check: n=2 is even but prime, we correctly output 1 due to first condition.

    Now, are there any even numbers that are prime? Only 2. So fine.

    Now, we can also think about n=2^something, e.g., n=32 -> even -> 2. Indeed 19+13=32 both primes.

    Now, let's test n=1000000000 (1e9). Even -> 2.

    Thus, solution is done.

    But before final, I'll re-derive from first principles to ensure no missed case.

    Define f(n) = minimal total tax.

    We know f(prime) = 1 (by taking whole).

    For composite n, we can consider splits.

    Observation: For any part x, tax(x) = 1 if x prime, else tax(x) ≥ 2. Actually, could tax(x) = 2 only for x=4, else if x composite and x>4, tax(x) ≥ 3? Check x=6 tax=3, x=8 tax=4, x=9 tax=3, x=10 tax=5, x=12 tax=6, x=14 tax=7, x=15 tax=5, x=16 tax=8, x=18 tax=9, x=20 tax=10, x=21 tax=7, x=22 tax=11, x=24 tax=12, x=25 tax=5, x=26 tax=13, x=27 tax=9, x=28 tax=14, x=30 tax=15, etc. So minimal composite tax for x≥6 is 3 (for 6 and 9). But note x=4 gives tax=2. So only 4 gives tax=2. Also x could be 2? prime =>1.

    Thus, if we use any composite part besides 4, that part contributes at least 3. So using a composite part larger than 4 likely increases total.

    Now, consider splitting into k parts. Let a be number of prime parts (each contribute 1), b be number of composite parts (each contribute at least 2, but for composite =4 contributes exactly 2, others ≥3). Then total tax = a + sum_{composites} tax(ci) ≥ a + 2b (if all composites are 4) or more.

    And we have sum of parts = n, with each part ≥2.

    Goal: minimize total tax.

    We can attempt to use as many primes as possible, but also limit number of parts because total tax at least k (if all primes). So we want to minimize k, but we can only use primes for each part. So the minimal k for which n can be expressed as sum of k primes is crucial. That's the prime partition length. Known: any integer > 1 can be expressed as sum of at most 3 primes (Goldbach's weak for odd >5, and Goldbach strong for even >2). Actually, every integer greater than 5 can be expressed as sum of at most 3 primes? Goldbach's weak says every odd number greater than 5 can be expressed as sum of three primes, but even numbers can be expressed as sum of two primes (Goldbach strong). So for n>2, the minimal number of primes needed (call s(n)) is: if n is prime ->1; else if n is even ->2; else if n is odd composite -> if n-2 is prime ->2 else 3. And we also need to consider that parts must be >=2, which holds for primes (smallest prime is 2). So indeed f(n) = s(n) because we can achieve total tax = s(n) by using s(n) primes (each tax=1). And we cannot get less than s(n) because any split with fewer than s(n) parts would require at least one composite (since we can't represent n as sum of fewer primes), and that composite will increase total tax such that total ≥ (k-1)*1 + 2 = k+1 if composite is 4, or more otherwise. But could k+1 be less than s(n)? Suppose s(n)=3 and k=2, then total tax ≥ 3 if we use one composite 4 and one prime => 3. So it's possible to achieve total = 3 with k=2 if composite=4 and prime exists. That matches s(n)=3? Actually if s(n)=3, then minimal prime partition length is 3. But if we can achieve total tax=3 with k=2 using a composite 4 and a prime, then we would have total tax=3, which equals s(n)=3. But could it be less? For k=2, total tax ≥ 1+2=3 (since composite tax ≥2), so cannot be less than 3. So f(n) = 3, same as s(n). So indeed f(n) = s(n). But is there any case where using composite yields total tax < s(n)? For s(n)=2, k=2 gives total tax =2 if both primes, or could k=1 (no split) give total tax 1? No, because n is composite so tax(n) >1, typically ≥2. But could tax(n)=2? For n=4, tax=2, which equals s(4)=2. For n=6, tax=3 >2. So f(n) >=2, and we can achieve 2 by two primes. So f(n)=2. For s(n)=1 (n prime), f(n)=1. So indeed f(n)=s(n). And the formula for s(n) is as above.

    Thus, we are safe.

    Now, let's also consider n=2? s(2)=1, f(2)=1.

    Now, also consider n=3? s=1, f=1.

    Now, consider n=4? s=2, f=2.

    Now, n=5? s=1.

    Now, n=6? s=2? 6 is even, so s=2? But is 6 expressible as sum of two primes? 3+3=6, yes. So s=2, f=2.

    Now, n=8? s=2, f=2.

    Now, n=9? s=2 because 2+7, so f=2.

    Now, n=10? s=2.

    Now, n=11? s=1.

    Now, n=12? s=2.

    Now, n=13? s=1.

    Now, n=14? s=2.

    Now, n=15? s=2.

    Now, n=16? s=2.

    Now, n=17? s=1.

    Now, n=18? s=2.

    Now, n=19? s=1.

    Now, n=20? s=2.

    Now, n=21? s=2.

    Now, n=22? s=2.

    Now, n=23? s=1.

    Now, n=24? s=2.

    Now, n=25? s=2.

    Now, n=26? s=2.

    Now, n=27? s=3? 27=2+2+23? Actually 2+2+23=27, yes three primes, and cannot be sum of two primes because 27-2=25 not prime, so s=3. So f=3.

    Now, n=28? even s=2.

    Thus, matches.

    Now, answer = minimal number of primes needed to represent n as sum of primes, but capped at 3? Actually it's at most 3, but for prime n it's 1. For even n (composite) it's 2. For odd composite, it's 2 if n-2 is prime else 3.

    Thus, solution.

    Now, we could also use this logic: answer = 1 if n is prime; else if n%2==0 or isPrime(n-2) then 2 else 3.

    Now, we need to make sure isPrime(n-2) called only when n is odd, and n>=5? For n=3, we don't call because n is prime. For n=5 prime. For n=7 prime. For n=9 odd composite, n-2=7, ok.

    Now, if n=2? prime.

    Now, what about n=4? even, we go to else if n%2==0, answer 2. Good.

    Now, check n=1? not allowed.

    Thus, final.

    Now, we may add slight optimization: For n even and n>2, answer 2; for n odd and not prime, check if n-2 prime. But we must ensure n-2 >1? n odd composite min is 9, n-2=7 >1. So fine.

    Now, think about n=2? even but prime, we already handled with prime check.

    Thus, code.

    Now, let's also verify n=2e9-1? It's odd. Check if it's prime? Possibly not, but we can test quickly? But we don't need to compute actual. Our code will compute is_prime for that number (2e9-1 = 1999999999). That number? I'm not sure if it's prime. But we'll compute via trial division. That may be heavy? 2e9-1 ~ 44721 iterations, still fine. Also check n-2 = 1999999997. Two primality tests. That's about 44721*2 = 89442 divisions, which is fine in Python (<0.1 sec). So okay.

    But one nuance: In Python, while i*i <= x can be slower due to big integer multiplication, but still fine.

    To be safe, we can compute limit = int(math.isqrt(x)) (Python 3.8 has math.isqrt). Then for i from 3 to limit step 2. That may be faster. We'll use math.isqrt.

    Implementation:

    def is_prime(x): if x < 2: return False if x % 2 == 0: return x == 2 limit = int(math.isqrt(x)) for i in range(3, limit+1, 2): if x % i == 0: return False return True

    That's efficient.

    Now, final code:

    import sys, math

    def is_prime(x): if x < 2: return False if x % 2 == 0: return x == 2 limit = math.isqrt(x) for i in range(3, limit+1, 2): if x % i == 0: return False return True

    def solve(): n = int(sys.stdin.readline()) if is_prime(n): print(1) else: if n % 2 == 0: print(2) else: if is_prime(n-2): print(2) else: print(3)

    if name == "main": solve()

    Now, one more edge: When n is odd and not prime, and n-2 is 1? Could happen if n=3? But we already handled prime case. n=1 not allowed. So fine.

    Now, ensure we import math.

    Now, final answer.

    But I recall that Codeforces problem might have had constraints up to 10^12? Actually original problem "C. Taxes" maybe had n up to 10^12? Let's check memory: I think problem "C. Little Pony and Summer Sun Celebration"? Not that. I'm trying to recall. Actually the problem "Taxes" from Codeforces Round #735 (Div. 2) had n up to 2·10^9. Yes. So it matches.

    Thus, final solution.

    Now, double-check the logic with an odd composite where n-2 not prime but we can use 4? That gives total 3 anyway. So our answer 3 is correct.

    Now, verify n=95: n=95, odd composite, n-2=93 composite, so answer=3. Is there a split that yields total=3? Need either three primes (tax=3) or two parts with one prime and 4. 95-4=91 composite, so 4+91 yields tax 2+? 91 spf=7? tax=13? total=15. Not 3. 2+93 gives 1+? 93 tax=31? 93/3=31, total=32. So three primes? 95 = 2+2+91? 91 composite, not prime. 3+5+87? 87 composite. Need three primes sum to 95. Possibility: 2+2+91? no; 3+3+89? 89 prime, 3+3+89=95, all primes, yes. So three primes works: 3,3,89 => taxes 1+1+1=3. So answer=3. So fine.

    Thus, algorithm correct.

    Now, finalize.

    But we must also ensure that we don't need to handle n=2 as even. Already.

    Now, writing final answer.

    One more nuance: In some definitions, 1 is not a prime, but we treat it as not prime. So is_prime(1) false.

    Now, done.

    Now, I'll produce final answer in the required format. ```python

    import sys import math

    def is_prime(x: int) -> bool: """Return True if x is prime, False otherwise.""" if x < 2: return False if x % 2 == 0: return x == 2 limit = math.isqrt(x) for i in range(3, limit + 1, 2): if x % i == 0: return False return True

    def solve() -> None: n = int(sys.stdin.readline().strip())

    if is_prime(n):
        print(1)
    else:
        if n % 2 == 0:
            print(2)
        else:
            # n is odd and composite
            if is_prime(n - 2):
                print(2)
            else:
                print(3)
    

    if name == "main": solve()