1719 測資加強 已 rejudge
1349 . [特別加考題] 平方國的平方幣
Description
平方國的人民對於完全平方數總是情有獨鍾。
就拿他們的貨幣來說吧，平方幣的幣值永遠是完全平方數，而且你所想像的任何完全平方幣值都有。
不過當外地旅客到平方國旅遊的時候，付錢卻成了令人頭痛的問題，當地人稱呼這種現象叫做「平幣效應」。
是的，你必須打破這種效應，於是你決定了，不管是任何金額，你總是可以支付最少張數的錢幣。
寫個程式吧，算起來比較快！
Input Format
輸入可能包含多筆測試資料，每一筆測試資料佔一列，僅包含一個正整數 N (1<=N<=10,000,000)。
當N=0時代表輸入結束。
Output Format
請輸出用最少幾張平方幣可以湊出該輸入金額。
Sample Input 1
1
2
3
4
5
6
7
0
2
3
4
5
6
7
0
Sample Output 1
1
2
3
1
2
3
4
2
3
1
2
3
4
Hints
Problem Source
原TIOJ1349 / Problem Setter: Tmt
EXTREME version of Ural 1073
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |