69. 節稅計畫

節稅計畫

題目敘述

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