Integer square root

Problem

Read a whole number n and print the largest whole number x such that x * x ≤ n. Solve it with a binary search, not with a square-root function.

Example 1

Input

Output

Example 2

Input

Output

Try the problem first. Open one hint at a time.

Hint 1

The check x * x ≤ n is true for small x and false for large x, so the answer is the last x where it is true.

Hint 2

Use the upper middle, (lo + hi + 1) // 2, when you keep mid with lo = mid.

Write your Python code, run it on the examples and submit it to hidden tests.