69. 節稅計畫

0 Judge

Code: 0


節稅計畫

題目敘述

sprout

Allen成為大老闆之後賺了大量的財富。被眼尖的查稅員給盯上了,於是只好乖乖地把所有項目公開出來。這個國家的稅法有一點奇怪,如果一個人的所得是N元,那他要繳的稅金等於小於N的除數中最大得除數,比如說所得是60000元的話,要繳交30000元,高達收入的50%,非常的可怕。

為了避免高額的稅金,報告所得時可以分成很多份,每一份都分開來計算繳交的稅金,但是不得低於1元,比如說原本10元要繳交5元的稅金,分成5,5則只需要繳交1+1元的稅金,十分的划算。

不過計算最低需要繳交多少稅金十分麻煩,你可以幫幫Allen嗎?

輸入說明

有多筆測資,每筆測資包含一個數N,表示Allen的輸入,保證:

$2\leq N \leq 2\times 10^9$

輸出說明

對於每筆測資輸出一行,為Allen最低需繳交的稅金為何。

範例輸入

4
5

範例輸出

2
1

配分方法

配分 限制
5% $N\leq 10$
25% $N\leq 10000$
20% $N$是偶數
50% 沒有限制
時限 100ms
記憶體 5120000 kb

Judge Setting

run-time limit: 100 ms
memory limit: 5120000 byte
測資數量: 0