def sqrt(n):
    """sqrt(non_negative_integer) -> integer

    Return integer square root of an input number """
    if n == 0:
        return 0
    x = 2 ** sum(divmod(n.bit_length(), 2))
    while True:
        y = x + n // x
        y //= 2
        if y >= x:
            return x
        x = y
