x 的平方根

题目描述

给定一个非负整数 x，请计算并返回 x 的算术平方根的整数部分。

返回结果只保留整数部分，小数部分将被舍去。

不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或 x ** 0.5。

输入格式

输入一行，包含一个非负整数 x。

输出格式

输出一个整数，表示 x 的算术平方根的整数部分。

数据范围

0 <= x <= 2^31 - 1

样例 1

输入

4

输出

2

样例 2

输入

8

输出

2

说明

8 的算术平方根约为 2.82842...，其整数部分为 2。