Integer Square Root

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given a nonnegative integer $n$, find the greatest nonnegative integer $k$ satisfying $k^2\le n$. This is the integer square root of $n$; the answer must be exact rather than inferred from floating-point rounding.

Input

One line contains a nonnegative integer $n$.

Output

Print the integer $k=\lfloor\sqrt n\rfloor$.

Subtasks

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

Examples

Example 1

Input

26

Output

5

Explanation

$5^2=25\le26$ while $6^2=36>26$, hence the answer is 5.

Example 2

Input

0

Output

0

Explanation

$0^2=0\le0$ but $1^2>0$, so the answer is zero.

Example 3

Input

1000000000000

Output

1000000

Explanation

$1000000^2=10^{12}$, giving the exact integer square root.