from random import randrange


def primes(n):
    """primes(n) returns the list of primes <n"""
    return [p for p in range(2,n) if 0 not in [p%d for d in range(2,p) if d*d<=p]]

def eratosthenes(n):
    """
    eratosthenes(n) returns the list of all primes <n using the sieve method
    """
    d={}
    for i in range(2,n):
        d[i]=1
    arrow=2
    while arrow*arrow<n:
        for k in range(2,n/arrow+1):
            d[k*arrow]=0
        arrow=arrow+1
        while arrow<n and d[arrow]==0:
            arrow=arrow+1
    return [p for p in range(2,n) if d[p]==1]

def isprime(n):
    """
    isprime(n) for integer n>1 returns 1 if n is prime, 0 if n is composite
    """
    k=2
    while k*k<=n:
        if n%k==0:
            return 0
        k=k+1
    return 1

def factor(n):
    k=2
    while k*k<=n:
        if n%k==0:
            return [k]+ factor(n/k)
        k=k+1
    return [n]
    

def gcd(a,b):
    """
    gcd(a,b) for positive integers a,b returns gcd(a,b), duh
    """
    if b==0: return a
    r=a%b
    return gcd(b,r)
    

def egcd(a,b):
    """
    egcd(a,b) for a,b>0 returns g,x,y where g=gcd(a,b) and xa+yb=g
    """
    
    if b==0: return a,1,0
    q,r=divmod(a,b)
    g,y,x=egcd(b,r)
    return g,x,y-x*q


def cf2frac(L):
    """
    returns p,q where the value of the cf is p/q
    L is a list, where [a_0,a_1,...,a_n] corresponds to
    a_0+1/a_1+1/a_2...+1/a_n
    """
    if len(L)==1:
        return L[0],1
    L1=L[1:]
    p,q=cf2frac(L1)
    return L[0]*p+q,p


def real2cf(x,n):
    """
    returns L=[a_0,a_1,...,a_n], the initial piece of the cf expansion of x
    """
    if n==0:
        return [int(x)]
    k=int(x)
    L1=real2cf(1./(x-k),n-1)
    return [k]+L1

def powermod2(a,k,m):
    # computes a^k mod m recursively
    if k==1: return a%m
    b=(a**2)%m
    if k%2==0:
        return powermod2(b,k/2,m)
    else:
        return a*powermod2(b,(k-1)/2,m)%m

def powermod(a,k,m):
    # computes a^k mod m
    ret,aa,kk = 1,a,k
    # ret*aa**kk with smaller and smaller kk
    while kk>0:
        if kk%2==0:
            kk = kk/2
            aa = (aa**2)%m
        else:
            kk = kk-1
            ret = ret*aa % m
    return ret


def invmod(a,m):
    # finds multiplicative inverse of a mod m, assuming gcd(a,m)=1
    g,u,v=egcd(a,m)
    return u%m



def miller_rabin(n,tests=4):
    # tests if number n is prime, 0 means composite, 1 means probably prime
    if n<2: return 0
    if n==2: return 1
    if n%2==0: return 0
    d=n-1
    s=0
    while d%2==0:
        s=s+1
        d=d/2
    # now n-1=d*2**s with d odd
    for i in range(tests):
        a=randrange(1,n)
        b=powermod(a,d,n)
        if b!=1:
            j=0
            res=0
            while j<s and b!=n-1:
                b=(b*b)%n
                j=j+1
            if j==s:
                    return 0
    return 1


def randprime(b):
    # random prime with b digits
    while 1:
        p=randrange(10**(b-1),10**b)
        if miller_rabin(p):
            return p
            
def primefactors(n):
    # list of prime factors of n
    if n<2: return []
    q=2
    while q*q<=n:
        if n%q==0:
            L=primefactors(n/q)
            if q in L:
                return L
            else:
                return [q]+L
        q=q+1
    return [n]



def primitive(p):
    # assuming p is prime finds a primitive element mod p
    if p==2: return 1
    a=2
    L=primefactors(p-1)
    
    while 1:
        flag=1
        for s in L:
            if powermod(a,(p-1)/s,p)==1:
                flag=0
                break
        if flag==1:
            return a
        a=a+1