<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

111. Very simple problem

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


You are given natural number X. Find such maximum integer number that it square is not greater than X.


Input

Input file contains number X (1≤X≤101000).


Output

Write answer in output file.


Sample Input

16
Sample Output

4

<|response|>
1. Abridged Problem Statement  
Given a (possibly very large) natural number X (1 ≤ X ≤ 10¹⁰⁰⁰), compute the greatest integer R such that R² ≤ X.  

2. Key Observations  
- The function f(R)=R² is strictly increasing for R≥0.  
- Therefore the integer square root R=⌊√X⌋ can be found by binary searching R in a range [0…U], as long as U≥√X.  
- Since X can have up to 1000 decimal digits, built-in types (32- or 64-bit) overflow; we need an arbitrary-precision integer library or language support.  
- Each binary-search step requires one big-integer multiplication mid·mid and one big-integer comparison to X.  
- If X has d digits, then √X has about ⌈d/2⌉ digits; setting U=10^(⌈d/2⌉+1) guarantees U²>X.  
- Total cost is O(log U) big-integer multiplications; for d≈1000, this is efficient if using e.g. Karatsuba or the built-in big-int engine.  

3. Full Solution Approach  
a. Read X as a string.  
b. Let d = length of that string.  
c. Compute an upper bound U = 10^((d+1)/2 + 1).  
d. Initialize low = 0, high = U, answer = 0.  
e. While low ≤ high:  
   • mid = (low + high) // 2  
   • compute mid²  
   • if mid² ≤ X: answer = mid; low = mid + 1  
     else: high = mid - 1  
f. Print answer.  

The entire logic rests on binary search and big-integer arithmetic for multiply and compare.  

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

// Read a big integer from stdin
cpp_int read_bigint() {
    string s;
    if(!(cin >> s)) {
        return 0;
    }
    cpp_int x = 0;
    for(char c : s) {
        x *= 10;
        x += (c - '0');
    }
    return x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1. Read X
    cpp_int X = read_bigint();

    // 2. Determine number of decimal digits in X
    //    We can re-convert to string, or count digits of input.
    //    Here we reuse to_string:
    string xs = X.convert_to<string>();
    int d = (int)xs.size();

    // 3. Compute an upper bound U = 10^((d+1)/2 + 1)
    //    This guarantees U^2 > X.
    int half_plus = (d + 1)/2 + 1;
    cpp_int U = 1;
    for(int i = 0; i < half_plus; i++){
        U *= 10;
    }

    // 4. Binary search for floor(sqrt(X))
    cpp_int low = 0, high = U, ans = 0;
    while(low <= high) {
        cpp_int mid = (low + high) >> 1;   // (low + high) / 2
        cpp_int sq = mid * mid;
        if(sq <= X) {
            ans = mid;         // mid is a valid candidate
            low = mid + 1;     // try to go higher
        } else {
            high = mid - 1;    // mid is too big
        }
    }

    // 5. Output the result
    cout << ans << "\n";
    return 0;
}
```

Explanation of key points:  
- We use Boost.Multiprecision’s `cpp_int` for arbitrary-precision integers.  
- We derive an upper bound U by taking one extra digit beyond half the length of X.  
- Binary search invariants: at each step `ans` holds the largest R so far with R²≤X.

5. Python Implementation with Detailed Comments  
```python
import sys

def isqrt_binary(X: int) -> int:
    """
    Compute floor(sqrt(X)) by binary search.
    """
    # Number of decimal digits of X
    d = len(str(X))
    # Upper bound: 10^((d+1)//2 + 1)
    high = 10 ** (((d + 1)//2) + 1)
    low = 0
    ans = 0
    while low <= high:
        mid = (low + high) // 2
        sq = mid * mid
        if sq <= X:
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    return ans

def main():
    data = sys.stdin.read().strip()
    if not data:
        return
    X = int(data)  # Python int is arbitrary-precision
    try:
        # Python ≥3.8 provides math.isqrt which is much faster
        import math
        result = math.isqrt(X)
    except (ImportError, AttributeError):
        # Fallback to manual binary search
        result = isqrt_binary(X)
    # Print the floor of the square root
    sys.stdout.write(str(result))

if __name__ == "__main__":
    main()
```

Notes on the Python version:  
- We first try to use `math.isqrt`, which directly computes the integer square root in O(n·log²n) or better.  
- If `math.isqrt` is unavailable, we fall back to a manual binary search over `[0…10^((d+1)//2 + 1)]`.  
- Converting the input string to `int` handles arbitrary sizes seamlessly.