{"raw_statement":[{"iden":"statement","content":"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.\n\nAs 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_.\n\nOstap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split _n_ in parts."},{"iden":"input","content":"The first line of the input contains a single integer _n_ (2 ≤ _n_ ≤ 2·109) — the total year income of mr. Funt."},{"iden":"output","content":"Print one integer — minimum possible number of burles that mr. Funt has to pay as a tax."},{"iden":"examples","content":"Input\n\n4\n\nOutput\n\n2\n\nInput\n\n27\n\nOutput\n\n3"}],"translated_statement":[{"iden":"statement","content":"Mr. Funt 现在生活在一个税收法律非常特殊的国家。Mr. Funt 今年的总收入为 $n$（$n ≥ 2$）布尔，他需要缴纳的税款为 $n$ 的最大真因子（即不超过 $n$ 且不等于 $n$ 的最大因子）。例如，若 $n = 6$，则 Funt 需支付 $3$ 布尔；若 $n = 25$，则需支付 $5$ 布尔；若 $n = 2$，则只需支付 $1$ 布尔。\n\n由于 Mr. Funt 是一个非常善于投机的人，他想稍微作弊一下。具体来说，他想将初始的 $n$ 拆分成若干部分 $n_1 + n_2 + ... + n_k = n$（这里 $k$ 可以是任意正整数，甚至允许 $k = 1$），并对每一部分分别缴税。他不能让任何一部分等于 $1$，因为那样会暴露他。因此，对所有 $i$ 从 $1$ 到 $k$，必须满足 $n_i ≥ 2$。\n\nOstap Bender 想知道，如果 Funt 选择最优的拆分方式，他最少需要支付多少税款。\n\n输入的第一行包含一个整数 $n$（$2 ≤ n ≤ 2·10^9$）— Mr. Funt 的年总收入。\n\n请输出一个整数 — Mr. Funt 最少需要支付的税款（以布尔为单位）。"},{"iden":"input","content":"输入的第一行包含一个整数 $n$（$2 ≤ n ≤ 2·10^9$）— Mr. Funt 的年总收入。"},{"iden":"output","content":"请输出一个整数 — Mr. Funt 最少需要支付的税款（以布尔为单位）。"},{"iden":"examples","content":"输入\n4\n输出\n2\n输入\n27\n输出\n3"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the total income.  \nFor any integer $ m \\geq 2 $, define $ T(m) $ as the largest proper divisor of $ m $, i.e., $ T(m) = \\max\\{ d \\mid d \\mid m, 1 \\leq d < m \\} $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 2 \\cdot 10^9 $  \n2. A partition of $ n $ is a tuple $ (n_1, n_2, \\dots, n_k) $ with $ k \\geq 1 $, $ n_i \\geq 2 $ for all $ i $, and $ \\sum_{i=1}^k n_i = n $.  \n\n**Objective**  \nMinimize the total tax:  \n$$\n\\min_{\\substack{(n_1,\\dots,n_k) \\\\ \\sum n_i = n \\\\ n_i \\geq 2}} \\sum_{i=1}^k T(n_i)\n$$","simple_statement":null,"has_page_source":false}