Calculate a Square Root by Hand

Problem Description

Write a function that returns the square root of a positive integer, rounded down to the nearest integer, without using the sqrt() function.

Input

• A positive integer.

Output

• An integer that is the square root of the input, rounded down to the nearest integer.

Constraints

• The input will always be a positive integer.

Example

Input:
9

Output:
3

Explanation:
The square root of 9 is exactly 3.

Input:
16777216

Output:
4096

Explanation:
The square root of 16777216 is 4096.

Input:
16

Output:
4

Explanation:
The square root of 16 is exactly 4.

Input:
15

Output:
3

Explanation:
The square root of 15 is approximately 3.872, which rounds down to 3.