# Miller-Rabin法

def is_prime(n):
    
    # a_list = [2, 3, 5, 7, 11]
    
    a_list = [
    2,
    325,
    9375,
    28178,
    450775,
    9780504,
    1795265022,
    ]

    if n <= 2: return n == 2
    if n % 2 == 0: return False
    d = (n-1) // ((n-1)&(1-n))
    for a in a_list:
        t = d
        a = pow(a, t, n)
        if a == 0 or a == 1: continue
        while a != n-1:
            t *= 2
            if t == n-1: return False
            a = a * a % n
            if a == 1: return False
    return True