Số chính phương rất lớn (Very Big Perfect Squares)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một số nguyên là số chính phương nếu nó có dạng $m^2$ với một số nguyên $m$.

Cho số tự nhiên rất lớn $A$. Số lượng số chính phương trong đoạn từ $1$ đến $A$ là $\lfloor\sqrt A\rfloor$.

Tuy nhiên, không cần in toàn bộ giá trị này. Chỉ giữ chữ số có nghĩa đầu tiên của kết quả và thay mọi chữ số phía sau bằng 0. Ví dụ, nếu số lượng thật sự là $59$ thì in 50; nếu là $12345$ thì in 10000.

Input

Một dòng chứa số tự nhiên $A$ ở hệ thập phân.

Output

In số lượng số chính phương từ $1$ đến $A$ theo dạng xấp xỉ được mô tả: giữ chữ số đầu tiên và thay các chữ số còn lại bằng 0.

Subtask

• Subtask 1 (20%): $1\le A\le10^{18}$.
• Subtask 2 (30%): $A$ có không quá $100$ chữ số.
• Subtask 3 (50%): Đầy đủ: $1\le A\le10^{1000}$.

Ví dụ

Input

1000

Output

30

Giải thích

Có $\lfloor\sqrt{1000}\rfloor=31$ số chính phương không vượt quá $1000$. Theo yêu cầu chỉ giữ chữ số đầu tiên của 31 và thay chữ số còn lại bằng 0, nên output là 30.