Căn bậc hai nguyên (Integer Square Root)

Nguồn: Phước Hưng OJ

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

Đề bài

Cho số nguyên không âm $n$. Tìm số nguyên không âm lớn nhất $k$ sao cho $k^2\le n$. Giá trị cần tìm là phần nguyên của căn bậc hai của $n$; không sử dụng kết quả làm tròn số thực để quyết định đáp án.

Input

Một dòng chứa số nguyên không âm $n$.

Output

In số nguyên $k=\lfloor\sqrt n\rfloor$.

Subtask

• Subtask 1 (20%): $0\le n\le10^4$.
• Subtask 2 (30%): $0\le n\le10^8$.
• Subtask 3 (50%): $0\le n\le10^{12}$.

Ví dụ

Ví dụ 1

Input

26

Output

5

Giải thích

$5^2=25\le26$ còn $6^2=36>26$, nên số nguyên lớn nhất cần tìm là 5.

Ví dụ 2

Input

0

Output

0

Giải thích

$0^2=0\le0$ nhưng $1^2=1>0$, nên kết quả là 0.

Ví dụ 3

Input

1000000000000

Output

1000000

Giải thích

$1000000^2=10^{12}$, vì vậy căn bậc hai nguyên đúng bằng 1000000.