import random
from math import gcd

def isPrime(m):
    '''Check whether m is a prime number'''
    if m in (2, 3, 5, 7):
        return True
    if m <= 10 or m%2 == 0:
        return False
    d = 3
    while d*d <= m:
        if m%d == 0:
            return False
        d += 2
    return True
    
def factor(m):
    '''Factorize an integer m.
    Return a list of pairs (prime factor, its exponent).
    Example: for m = 60 the result is [(2, 2), (3, 1), (5, 1)]'''    
    if type(m) != int:
        raise ValueError("non-integer argument of factor(m)")
    if m == 0:
        return [(0, 1)]
    factors = []
    if m < 0:
        m //= (-1)
        factors.append((-1, 1))
    assert m > 0
    
    d = 2
    while d*d <= m:
        if m%d == 0:
            e = 0
            while m%d == 0:
                m //= d
                e += 1
            factors.append((d, e))
        d += 1
    if m > 1:
        factors.append((m, 1))
    return factors
            
def f(x, m):
    return (x*x + 1)%m

def pollardRhoFactor(m, maxSteps = 10000000):
    '''Find a nontrivial divisor of m.
    Return 1 if this is not possible'''
    if m > 4:
        x = random.randrange(2, m-1)    # Initial point
    else:
        x = 2
        
    y = f(x, m)
    d = gcd(x - y, m)
    step = 0
    while d == 1 and step <= maxSteps:
        x = f(x, m)
        y = f(y, m)
        y = f(y, m)
        d = gcd(x - y, m)
        step += 1
    if d == m:
        d = 1
    return d