def isqrt(x: int) -> int:
    """ Returns the largest integer y such that y * y <= x """
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    elif x == 0:
        return 0
    n = x
    a, b = divmod(n.bit_length(), 2)
    x = 2 ** (a + b)
    while True:
        y = (x + n // x) // 2
        if y >= x:
            return x
        x = y