def gcd(a, b):
    while b>0: a, b = b, a % b
    return a

def simplify(a, b):
    d = gcd(a, b)
    return (a / d, b / d)

def add((a, b), (c, d)):
    return simplify(a * d + b * c, b * d)

def mul((a, b), (c, d)):
    return simplify(a * c, b * d)

def euclid(a, b):
    p = q = y = u = 0
    x = v = 1
    while b>0:
        p, a, q, b = (q,b) + divmod(a,b)
        x, y, u, v = u, v, x - q * u, y - q * v
    return x, y, a

def confrac(a, b):
    d = divmod(a, b)
    if d[1]==0:
        return (d[0],)
    else:
        return (d[0],) + confrac(b, d[1])

def fract(con):
    r, p = 0, 1
    s, q = 1, 0
    for i in con:
        r, p = p, r + i * p
        s, q = q, s + i * q
    return (p, q)

def chin(a, b):
    i = 0
    r, p = 0, 1
    s, q= 1, 0
    while b>0:
        i = i + 1
        d = divmod(a, b)
        r, p = p, d[0] * p + r
        s, q = q, d[0] * q + s
        a, b = b, d[1]
    return (a, (-1)**i * s,-(-1)**i * r)

def modsum(x, y, m):
    return (x + y) % m

def modprod(x, y, m):
    return (x * y) % m

def binary(x):
    bin=[]
    while x!=0:
        d = divmod(x,2)
        x, bin = d[0], [d[1]] + bin
    return bin

def modpower(x, y, m):
    bin = binary(y)
    result = 1
    for i in bin:
        result = modprod(result, result, m)
        if i==1:
            result = modprod(result, x, m)
    return result

def modinv(x, m):
    return euclid(x, m)[0] % m

def factors2(a):
    v2 = 0
    while a%2==0:
        a, v2 = a / 2, v2 + 1
    return a, v2

def jacobi(a, b):
    p = 0
    a,b = a % b, b
    if a==0: return 0
    f2 = factors2(a)
    a, b, p = f2[0], b, (f2[1] * ((b * b - 1) / 8) + p) % 2
    while a>1:
        a, b, p = b % a, a, ((a - 1) * (b - 1) % 8) / 4 + p % 2
        if a==0: return 0
        else:
            f2 = factors2(a)
            a, b, p = f2[0], b, (f2[1] * ((b * b - 1) / 8) + p) % 2
    return (-1)**p

import random

def sqrt(a, p):
    a = a % p
    p8 = p % 8
    if p8==3 or p8==7:
       return pow(a, (p + 1) / 4, p)
    if p8==5:
        x = pow(a, (p + 3) / 8, p)
        c = pow(x, 2, p)
        if c!= a: x = modprod(x, pow(2, (p - 1) / 4, p), p)
        return x
    if p8==1:
        d = 3
        while jacobi(d, p)==1:
            d = random.randint(2, p - 1)
        t, s = factors2(p - 1)
        A = pow(a, t, p)
        D = pow(d, t, p)
        m = 0
        for i in range(s):
            if pow(modprod(A, pow(D, m, p), p), 2**(s - 1 - i), p)\
            + 1==p:
                m = m + 2**i
        return modprod(pow(a, (t + 1) / 2, p),pow(D, m/2, p), p)

def trial_factors(n, N):
    factors = [n]
    while factors[-1] % 2==0:
        factors[-1:] = [2, factors[-1] / 2]
    d = 3
    while d**2<=factors[-1] and d<N:
        while factors[-1] % d==0:
            factors[-1:]=[d, factors[-1] / d]
        d = d + 2
    if factors[-1]==1: return factors[:-1]
    return factors

def trial_factorization(n):
    return trial_factors(n,n)

def eratosthenes(N):
    lst = N * [1]
    lst[:2] = [0, 0]
    i, j=2, 4
    while i**2<N:
        if lst[i]==1:
            j = i + i
            while j<N:
                lst[j] = 0
                j = j + i
        i = i + 1
    return lst

def primes(N):
    lst = eratosthenes(N)
    return filter(lambda i: lst[i]==1,range(N))

def factor_table(N):
    lst = N * [1]
    i, j = 2, 4
    while i**2<N:
        if lst[i]==1:
            j = i + i
            while j<N:
                if lst[j]==1: lst[j]=i
                j = j + i
        i = i + 1
    return lst

tbl=[]

def table_factorization(n):
    if len(tbl)<=n: tbl[:]=factor_table(n + 1)
    factors = []
    while tbl[n]!=1:
        factors.append(tbl[n])
        n = n / tbl[n]
    factors.append(n)
    return factors

def fermat(p, a):
    return pow(a, p, p)==a

def euler(p,a):
    j = (jacobi(a, p) % p)
    return  j!=0  and  pow(a, (p - 1) / 2, p)==j

def solovay(p, N):
    i=0
    while i<N:
        a = random.randint(2, p - 1)
        if not euler(p, a):
            return False
        i = i + 1
    return True

def strong(p, a):
    fact = factors2(p - 1)
    b = pow(a,fact[0], p)
    if b==1 or b==p - 1: return True
    j = 1
    while j<fact[1]:
        b = pow(b, 2, p)
        if b==p - 1: return True
        j = j + 1
    return False

def rabin(p,N):
    i = 0
    while i<N:
        a = random.randint(2, p - 1)
        if not strong(p, a):
            return False
        i = i + 1
    return True

def next_rabin_prime(a, N):
    a = a + (a % 2==0) + 2 * (a % 2==1)
    while not rabin(a, N):
        a = a + 2
    return a

def rabin_prob_primes(a, k, N):
    b = a + k
    a = a + (a % 2==0)
    primes=[]
    while a<b:
        if a % 3==0 or a % 5==0: a = a + 2
        else:
          if rabin(a, N):
            primes.append(a)
          a = a + 2
    return primes

def pepin(m):
    F=(2**(2**m)) + 1
    return pow(3, (F - 1) / 2, F)==F - 1

def pocklington(n, k, K):
    P=False
    while not P:
        a = random.randint(2,n - 1)
        if pow(a, n - 1, n)!=1: return False
        for q in K:
            g = gcd(pow(a, (n - 1) / q, n) - 1, n)
            if g!=n and g!=1: return False
            if g==n: break
        if g==1: P=True
    return True

def pollardrho(n):
    g = n
    while g==n:
        c = random.randint(1, n - 3)
        a = random.randint(0, n - 1)
        u = v = a
        def F(x):
            return (pow(x, 2, n) + c) % n
        g = 1
        while g==1:
            u = F(u)
            v = F(F(v))
            g = gcd(u - v, n)
    return g

def makersa(l):
    p = next_rabin_prime(random.randint(10**(l - 1), 9 * \
    (10**(l - 1))), 20)
    q = next_rabin_prime(random.randint((10**(2 * l)) / p,
    (10**(2 * l)) / p + (10**(l - 1))), 20)
    m = p * q
    e = random.randint(10**(2 * l - 1), 9 * (10**(2 * l - 1)))
    while gcd(e, (p - 1) * (q - 1))>1:
        e = e + 1
    f = modinv(e, (p - 1) * (q - 1))
    return (l, m, e), (l, m, f), (p, q)

def transform(nrlist, a, n):
    return [pow(nr, a, n) for nr in nrlist]

def encode_rsa(s, code):
    def number(c): return ord(c) - 32
    def str2(n): return str(n).zfill(2)
    def codenumber(s):
        return int(''.join(map(str2, map(number,list(s)))))
    def codenrs(lst): return [codenumber(s) for s in lst]
    return transform(codenrs([s[code[0] * i:code[0] * (i + 1)]
    .ljust(code[0]) for i in range(len(s)/code[0] + 1)]), 
    code[2], code[1])

def decode_rsa(nrlst, code):
    def char(n):
        if n>94: return r' '
        else: return chr(n + 32)
    def phrase(codenr, N):
        nrstr = str(codenr).zfill(N)
        return ''.join(map(char,map(int, [nrstr[2 * i:2 * i + 2]
        for i in range(len(nrstr) / 2)])))
    def phrases(nrlst, N):
        return [phrase(nr, N) for nr in nrlst]
    return r''.join(phrases(transform(nrlst,code[2],code[1]),
    2*code[0]))

def ent(alpha):
    return int(divmod(-alpha[1] + alpha[3] * (alpha[1]**2 - 4
    * alpha[0] * alpha[2])**.5, 2 * alpha[0])[0])

def sub(alpha, n):
    return (alpha[0], 2 * alpha[0] * n + alpha[1], alpha[0] * n**2
    + alpha[1] * n + alpha[2], alpha[3])

def inv(alpha):
    s=(-1)**(alpha[2]<0)
    return (s * alpha[2], s * alpha[1], s * alpha[0],-s * alpha[3])

def phi(alpha):
    return inv(sub(alpha, ent(alpha)))

def confrac(alpha):
    nrs = []
    exp = []
    while alpha not in nrs:
        a = ent(alpha)
        nrs.append(alpha)
        exp.append(a)
        alpha = inv(sub(alpha, a))
    i = nrs.index(alpha)
    return [exp[:i],exp[i:]]

def pell(d):
  alpha = (1,0,-d,1)
  e = a = ent(alpha)
  p, q, r, s = 0, 1, 1, 0
  i = 0
  b = 2 * e
  while a!=b:
      alpha = inv(sub(alpha, a))
      p, q, r, s = r, s, a * r + p, a * s + q
      a = ent(alpha)
      i = i + 1
  return (r, s, i)

def g_repr(a,b,g):
    nrs = []
    exp = []
    while a not in nrs:
        nrs.append(a)
        (c, a) = divmod(g * a, b)
        exp.append(c)
    i = nrs.index(a)
    return [exp[:i],exp[i:]]

def p_adic(a,b,p):
    u=modinv(b,p)
    nrs = []
    exp = []
    while a not in nrs:
        nrs.append(a)
        c = (a * u) % p
        a = (a - (c * b)) / p
        exp.append(c)
    i = nrs.index(a)
    return [exp[:i],exp[i:]]