12027 - Very Big Perfect Squares

Background

若整數 n 為完全平方數，表示存在有另一個整數 m 使得 n = m x m。例如前幾個完全平方數為1, 4, 9, 16, 25, 36...。

The Problem

給定一個自然數A，我們想要知道由1到A之間的所有整數中，共有幾個完全平方數(包含1與A)，例如由1到1之間只有一個完全平方數1，由1到5之間共有兩個(1與4)，1到40之間共6個(1, 4, 9, 16, 25, 36)。
由於A的值可能非常非常大，所以我們並不要求精確的答案，只需要最前面的一個位數正確就即可，之後的每個位數補0就好。

Input

輸入有多筆測試資料。每組測試資料一列，僅包含一個自然數A。A的值介於1 ~ 10^1000之間。最後一列為0表示測試資料結束。

Output

請輸出1到A之間共有幾個完全平方數，但是僅需最大的位數正確就好，其餘的補0，例如若結果為59，請你輸出50，若為12345，請輸出10000。

Sample Input

1
5
40
1000
0

Sample Output

1
2
6
30

---

原文出處