Find Square Root

Given a non-negative integer n, compute and return the integer square root of n.

Since the return type is an integer, the decimal part of the square root should be truncated (i.e., floor value).

You must not use any built-in exponent function or operator such as pow(n, 0.5) or n ** 0.5.

Example 1

Input

n = 16

Output

def sqrt(n) -> 4

Example 2

Input

n = 30

Output

def sqrt(n) -> 5

Explanation: √30 ≈ 5.477, truncated to 5.

Constraints:

• 0 <= n <= 10^18