정수 제곱근

0 이상 10^12 이하의 정수 n 이 주어집니다.

제곱해서 n 을 넘지 않는 가장 큰 정수를 출력하세요. 즉 k * k <= n 을 만족하는 가장 큰 k 입니다.

n 이 매우 클 수 있습니다. 1부터 하나씩 올려보지 말고 답을 이분 탐색해보세요.

예시

입력

16

출력

4