'''Number Theory'''
import random

def isPrime(m):
    if m in [2, 3, 5, 7, 11, 13, 17, 19]:
        return True
    if m%2 == 0 or m < 20:
        return False
    d = 3
    while d*d <= m:
        if m%d == 0:
            return False
        d += 2
    return True
    
def factorize(m):
    factors = []
    if m == 0:
        return factors
    if m < 0:
        factors.append((-1, 1))
        m = (-m)
    d = 2
    while m >= d:    
        if m%d == 0:
            e = 1
            m //= d
            while m%d == 0:
                e += 1
                m //= d
            factors.append((d, e))
        d += 1
    if m > 1:
        factors.append((m, 1))
    return factors
    
def powmod(x, n, m):
    assert(n >= 0)
    p = 1; y = x%m; k = n
    # Invariant: p * y^k == x^n (mod m)
    while k != 0:
        if k%2 == 0:
            k //= 2
            y = (y*y)%m
        else:
            k -= 1
            p = (p*y)%m
    return p
    
def gcd(m, n):
    assert m != 0 or n != 0
    (a, b) = (m, n)
    while b != 0:
        (a, b) = (b, a%b)
    if a > 0:    
        return a
    else:
        return (-a)
    
def extEucl(m, n):
    assert m != 0 or n != 0
    (a, b) = (m, n)
    u1 = 1; v1 = 0
    u2 = 0; v2 = 1
    while b != 0:
        q = a//b; r = a%b
        (a, b) = (b, r)
        (u1, u2) = (u2, u1 - q*u2)
        (v1, v2) = (v2, v1 - q*v2)
    if a > 0:
        return (a, u1, v1)
    else:
        return (-a, -u1, -v1)
        
def invmod(n, m):
    assert m != 0
    (d, u, v) = extEucl(m, n)
    if d != 1:
        raise ZeroDivisionError(
            "Element is not invertible modulo m"
        )   
    return v%m
    
def chineseReminderAlg(r1, r2, m1, m2):
    v = invmod(m1, m2)
    s = (v*(r2 - r1))%m2
    return r1 + s*m1
    
def squareSequence(b, m):
    assert m%2 != 0
    t = m - 1
    s = 0
    while t%2 == 0:
        t //= 2
        s += 1
    assert t*(2**s) == m - 1
    res = []
    x = powmod(b, t, m)
    res.append(x)
    for i in range(s):
        x = x*x%m
        res.append(x)
    return res
        
smallPrimes = [2, 3, 5, 7, 11, 13]
wheelLength = 1
for p in smallPrimes:
    wheelLength *= p
inversesModWheelLength = [
    d for d in range(1, wheelLength) if gcd(d, wheelLength) == 1
]

def spokedWheel(m):
    '''
    Find a factor of integer number m using the Spoked Wheel algorithm.
    Return 1 if m is prime.
    '''
    for d in smallPrimes:
        if m%d == 0:
            return d
    k = 0
    while True:
        for x in inversesModWheelLength:
            if k == 0 and x == 1:
                continue
            d = k*wheelLength + x
            if d*d > m:
                return 1
            if m%d == 0:
                return d
        k += 1