735D.md (1430B)
1 Source: https://codeforces.com/problemset/problem/735/D 2 3 D. Taxes 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 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 *n*1 + *n*2 + ... + *n**k* = *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 *n**i* ≥ 2 should hold for all *i* from 1 to *k*. 24 25 Ostap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split *n* in parts. 26 27 Input 28 29 The first line of the input contains a single integer *n* (2 ≤ *n* ≤ 2·109) — the total year income of mr. Funt. 30 31 Output 32 33 Print one integer — minimum possible number of burles that mr. Funt has to pay as a tax. 34 35 Examples 36 37 Input 38 39 ``` 40 4 41 ``` 42 43 Output 44 45 ``` 46 2 47 ``` 48 49 Input 50 51 ``` 52 27 53 ``` 54 55 Output 56 57 ``` 58 3 59 ```