def is_prime(N):
    """
    Тест Миллера-Рабина проверки числа на простоту.
    """
    if N < 2:
        return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
        if N % p == 0: return N == p
    d = N - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
        if a >= N: continue
        x = pow(a, d, N)
        if x == 1 or x == N - 1: continue
        for _ in range(s - 1):
            x = pow(x, 2, N)
            if x == N - 1: break
        else: return False
    return True

def primes(B):
    """
    Возвращает список всех простых чисел до B.
    """
    primes_list = []
    is_prime = [True] * (B + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, B + 1):
        if is_prime[p]:
            primes_list.append(p)
            for i in range(p * p, B + 1, p):
                is_prime[i] = False
    return primes_list

def first_primes(n):
    """
    Возвращает список первых n простых чисел.
    """
    primes_list = []
    candidate = 2
    while len(primes_list) < n:
        is_prime = True
        for p in primes_list:
            if p * p > candidate:
                break
            if candidate % p == 0:
                is_prime = False
                break
        if is_prime:
            primes_list.append(candidate)
        candidate += 1
    return primes_list

def is_smooth(n, base):
    """
    Проверяет, является ли число гладким относительно factor_base
    """
    if n == 0: return None
    fact = [0] * len(base)
    for i, p in enumerate(base):
        if n == 1: break
        while n % p == 0:
            n //= p
            fact[i] += 1
    if n != 1:
        return None
    return fact

def legendre(a, p):
    """Вычисление символа Лежандра"""
    if a % p == 0:
        return 0
    return pow(a, (p - 1) // 2, p)

def tonelli(n, p):
    """Реализует алгоритм Тонелли-Шенкса для нахождения квадратного корня числа"""
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    z = 2
    while legendre(z, p) != p - 1:
        z += 1
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    while t != 1:
        t2 = t
        i = 0
        while t2 != 1 and i < m:
            t2 = pow(t2, 2, p)
            i += 1
        b = pow(c, 2 ** (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r