codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```