{"problem":{"name":"D. Taxes","description":{"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 m","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF735D"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe first line of the input contains a single integer _n_ (2 ≤ _n_ ≤ 2·109) — the total year income of mr. Funt.\n\n## Output\n\nPrint one integer — minimum possible number of burles that mr. Funt has to pay as a tax.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Mr. Funt 现在生活在一个税收法律非常特殊的国家。Mr. Funt 今年的总收入为 $n$（$n ≥ 2$）布尔，他需要缴纳的税款计算为其最大真因子（即不超过 $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输入的第一行包含一个整数 $n$（$2 ≤ n ≤ 2·10^9$）— Mr. Funt 的年总收入。\n\n请输出一个整数 — Mr. Funt 所需缴纳的最少税款（以布尔为单位）。\n\n## Input\n\n输入的第一行包含一个整数 $n$（$2 ≤ n ≤ 2·10^9$）— Mr. Funt 的年总收入。\n\n## Output\n\n请输出一个整数 — Mr. Funt 所需缴纳的最少税款（以布尔为单位）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the total income.  \nFor any integer $ m \\geq 2 $, define $ f(m) $ as the largest proper divisor of $ m $, i.e., $ f(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 f(n_i)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF735D","tags":["math","number theory"],"sample_group":[["4","2"],["27","3"]],"created_at":"2026-03-03 11:00:39"}}