ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1593. Square Country. Version 2

Time limit: 1.0 second
Memory limit: 64 MB
There live square people in a square country. Everything in this country is square also. Thus, the Square Parliament has passed a law about a land. According to the law each citizen of the country has a right to buy land. A land is sold in squares, surely. Moreover, a length of a square side must be a positive integer amount of meters. Buying a square of land with a side a one pays a2 quadrics (a local currency) and gets a square certificate of a landowner.
One citizen of the country has decided to invest all of his N quadrics into the land. He can, surely, do it, buying square pieces 1 × 1 meters. At the same time the citizen has requested to minimize an amount of pieces he buys: "It will be easier for me to pay taxes," — he has said. He has bought the land successfully.
Your task is to find out a number of certificates he has gotten.

Input

The only line contains a positive integer N ≤ 1015 , that is a number of quadrics that the citizen has invested.

Output

The only line contains a number of certificates that he has gotten.

Sample

inputoutput
344
3

Notes

This problem is the same as “Square country” but with bigger limitations.
Problem Author: Prepared by Fyodor Menshikov, special thanks to Svyatoslav Demidov