TopCoder

Thumb ya2
赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

60.0% (6/10)

Submission's AC Ratio

35.0% (7/20)

Tags

Description

平方國的人民對於完全平方數總是情有獨鍾。

就拿他們的貨幣來說吧,平方幣的幣值永遠是完全平方數,而且你所想像的任何完全平方幣值都有。

不過當外地旅客到平方國旅遊的時候,付錢卻成了令人頭痛的問題,當地人稱呼這種現象叫做「平幣效應」。

是的,你必須打破這種效應,於是你決定了,不管是任何金額,你總是可以支付最少張數的錢幣。

寫個程式吧,算起來比較快!

Input Format

輸入可能包含多筆測試資料,每一筆測試資料佔一列,僅包含一個正整數 N (1<=N<=10,000,000)。
當N=0時代表輸入結束。

Output Format

請輸出用最少幾張平方幣可以湊出該輸入金額。

Sample Input

1
2
3
4
5
6
7
0

Sample Output

1
2
3
1
2
3
4

Hints

Problem Source

原TIOJ1349 / Problem Setter: Tmt
EXTREME version of Ural 1073

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144
1 5000 65536 262144