def use_math_gcd():
    global lengthsDict
    for m in range(2, size//2):
        for n in range(1, m):
            # m - num has to be odd
            if (m - n) % 2 == 1:
                msq = m * m
                nsq = n * n
                a = msq - nsq
                b = 2 * m * n
                c = msq + nsq
                length = a + b + c
                if length > size:
                    break
                if length <= size:
                    if math.gcd(a, b) == 1 and math.gcd(a, c) == 1 and math.gcd(b, c) == 1:
                        # if eu.primes.is_pythagorean_triple_primitive(a, b, c):
                        # print("Primitive ({},{},{}) --> {}".format(a,b,c,length))
                        mcount = 0
                        for mult in range(length, size + 1, length):
                            mcount += 1
                            # for each primitive and its multiples, add one to the possible ways of generating the length
                            if b > a:
                                # lengthsDict.setdefault(mult, []).append((a, b, c))
                                # primitives.add((a,b,c))
                                lengthsDict.setdefault(mult, []).append((mcount * a, mcount * b, mcount * c))
                            else:
                                # lengthsDict.setdefault(mult, []).append((b, a, c))
                                # primitives.add((b,a,c))
                                lengthsDict.setdefault(mult, []).append((mcount * b, mcount * a, mcount * c))

    def processor(iterator):
        for item in iterator:
            if item['fcontents']:
                tabdivisor = 0
                spacedivisor = 0
                for line in item['fcontents'].split('\n'):
                    tabs = 0
                    spaces = 0
                    for letter in line:
                        if letter == ' ':
                            spaces += 1
                        elif letter == '\t':
                            tabs += 1
                        else:
                            break
                    tabdivisor = gcd(tabdivisor, tabs)
                    spacedivisor = gcd(spacedivisor, spaces)
                    # click.echo('{} tabs {} spaces'.format(tabs, spaces))
                if spacedivisor > 0:
                    click.echo('{}: {} spaces'.format(item['filename'], spacedivisor))
                elif tabdivisor > 0:
                    click.echo('{}: {} tabs'.format(item['filename'], tabdivisor))


            yield item

def _brent(N):
    if N % 2 == 0:
        return 2
    y, c, m = random.randint(1, N - 1), random.randint(1, N - 1), random.randint(1, N - 1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = ((y * y) % N + c) % N
        k = 0
        while k < r and g == 1:
            ys = y
            for i in range(min(m, r - k)):
                y = ((y * y) % N + c) % N
                q = q * (abs(x - y)) % N
            g = math.gcd(q, N)
            k = k + m
        r = r * 2
    if g == N:
        while True:
            ys = ((ys * ys) % N + c) % N
            g = math.gcd(abs(x - ys), N)
            if g > 1:
                break

    return g

def p510(limit):
    t=time.clock()
    abc=[]
    for q in range(1,int(limit**0.5)+1):
        for p in range(1,q+1):
            if p*q%(p+q)==0:
                abc.append((p**2,q**2,(p*q//(p+q))**2))
    
#    abc=[(p**2,q**2,(p*q//(p+q))**2) for q in range(1,int(limit**0.5)+1) for p in range(1,q+1)if p*q%(p+q)==0]
    print(len(abc))
#    print(abc)
    print(time.clock()-t)
    abcfund=[]#set()
    for i in range(len(abc)):
        div=math.gcd(abc[i][0],math.gcd(abc[i][1],abc[i][2]))
        newTrio=(abc[i][0]//div,abc[i][1]//div,abc[i][2]//div)
        if newTrio not in abcfund:
            abcfund.append(newTrio)
    print("abcfund size: ",len(abcfund))
#    print(abcfund)
    print(time.clock()-t)
    S=0
    k=0
    for trio in abcfund:
        k+=1
        a,b,c=trio[0],trio[1],trio[2]
        L=limit//b
        S+=(a+b+c)*L*(L+1)//2
        if k%100==0:
            print(k,a,b,c,S,L)
    print(S)
    print(time.clock()-t)

def brent(n):
    g = 1
    while g == 1 or g == n:
        if n % 2 == 0:
            return 2
        y, c, m = random.randint(1, n - 1), random.randint(1, n - 1), random.randint(1, n - 1)
        g, r, q = 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = ((y * y) % n + c) % n
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = ((y * y) % n + c) % n
                    q = q * (abs(x - y)) % n
                g = math.gcd(q, n)
                k += m
            r += r
        if g == n:
            while True:
                ys = ((ys * ys) % n + c) % n
                g = math.gcd(abs(x - ys), n)
                if g > 1:
                    break
    return g

def p329hmmf(N=500,y=[0,0,0,0,1,1,0,0,0,1,0,0,1,0,1]):
    
    t0=time.clock()
    
    T=len(y) #length of sequence
    
    pinit=pif(N) #initial distribution
    A=tpmf(N) # transmission matrix
    B=epmf(N) # emission matrix
    
    alpha=np.zeros([T,N],dtype=object)
    
    # base case
    for i in range(N):
        alpha[0][i]=[B[y[0]][i][0]*pinit[i][0],B[y[0]][i][1]*pinit[i][1]]
    for i in range(1,T):
        for j in range(N):
            alpha[i][j]=[0,0]

    #step case
    for t in range(1,T):
        for i in range(N):
            s = [0,0]
            k=0
            while 1:
                if A[i][k][0]==0:
                    k+=1
                    continue
                else:
                    s[0] = A[i][k][0] * alpha[t-1][k][0]
                    s[1] = A[i][k][1] * alpha[t-1][k][1]
                    break
            for j in range(k+1,N):
                nnew=A[i][j][0] * alpha[t-1][j][0]
                if nnew==0:
                    continue
                dnew=A[i][j][1] * alpha[t-1][j][1]
                s[0]=s[0]*dnew+nnew*s[1]
                s[1]=s[1]*dnew
                gcd= math.gcd(s[0],s[1])
                s[0],s[1]=s[0]//gcd,s[1]//gcd
            alpha[t][i]=[0,0]    
            alpha[t][i][0] = B[y[t]][i][0] * s[0]
            alpha[t][i][1] = B[y[t]][i][1] * s[1]

    #final probability  
    s = [0,0];
    s[0]=alpha[T-1][0][0]
    s[1]=alpha[T-1][0][1]
    for i in range(1,N):
        nnew=alpha[T-1][i][0]
        if nnew==0:
            continue
        dnew=alpha[T-1][i][1]
        s[0]=s[0]*dnew+nnew*s[1]
        s[1]=s[1]*dnew
    gcd= math.gcd(s[0],s[1])
    
    print(str(s[0]//gcd)+'/'+str(s[1]//gcd))    
    print(time.clock()-t0)

def p540rm(N):
    
    t=time.clock()
    
    ctr=0
    
    for i in range(1,int((2*N/(1+(1+2**0.5)**2))**0.5)+1,2):
#        if i%2:
        n1=int(i//2**0.5+1)
        nv=int(((2*N-i*i)**0.5-i)//2)
#            print(n1,nv)
        for j in range(n1,nv+1):
            if math.gcd(i,j)==1:
                ctr+=1
    
    for i in range(1,int((N/(1+(1+2**0.5)**2))**0.5)+1):
        n1=int(i*2**0.5)+1
        nv=int((N-i*i)**0.5-i)
        for j in range(n1,nv+1):
            if j%2:
                if math.gcd(i,j)==1:
                    ctr+=1
     
    print(time.clock()-t)               
    print( ctr)

def _gcd_recursive(*args):
    """
    Get the greatest common denominator among any number of ints
    """
    if len(args) == 2:
        return gcd(*args)
    else:
        return gcd(args[0], _gcd_recursive(*args[1:]))

def to_verilator_cpp(top, verilog_prefix, sim_time=0):
    template_path = os.path.dirname(os.path.abspath(__file__))
    env = Environment(loader=FileSystemLoader(template_path))
    env.globals['zip'] = zip

    if hasattr(top, 'verilator_dumpfile'):
        dumpfile = top.verilator_dumpfile
    else:
        dumpfile = None

    clks = top.verilator_new_clock
    rsts = top.verilator_new_reset

    if hasattr(top, 'verilator_reset_statements'):
        inits_list = top.verilator_reset_statements
        inits = collections.OrderedDict()
        for init in inits_list:
            if isinstance(init, vtypes.Subst):
                inits[init.left] = init.right
    else:
        inits = {}

    ios = top.get_ports()
    inputs = [io_var for io_var in ios.values()
              if isinstance(io_var, vtypes.Input) and
              (io_var not in clks) and (io_var not in rsts)]

    time_step = None

    for hperiod in clks.values():
        if time_step is None:
            time_step = hperiod
        else:
            time_step = gcd(time_step, hperiod)

    for period, positive in rsts.values():
        if time_step is None:
            time_step = period
        else:
            time_step = gcd(time_step, period)

    if time_step is None:
        time_step = 1

    template_dict = {
        'verilog_prefix': verilog_prefix,
        'sim_time': sim_time,
        'time_step': time_step,
        'dumpfile': dumpfile,
        'clks': clks,
        'rsts': rsts,
        'inits': inits,
        'inputs': inputs,
    }

    template = env.get_template('verilator_template.cpp')
    code = template.render(template_dict)
    return code

def my_gcd(a, b):
    '''
    returns: str
    gcd for two given numbers
    '''
    if a == b or b == 0:
        return a
    elif a > b:
        return gcd(a-b, b)
    else:
        return gcd(b-a, a)

def resolve():
    import math
    n = int(input())
    dat_a = list(map(int, input().split()))
    dat_a = list(dat_a)
    m = []
    l = [0] * n
    r = [0] * (n + 1)
    l[0] = 0
    r[n - 1] = 0
    for i in range(n):
        l[i + 1] = math.gcd(l[i], dat_a[i])
        r[n - i-1] = math.gcd(r[n-i], dat_a[i])

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    import warnings
    warnings.warn('fractions.gcd() is deprecated. Use math.gcd() instead.',
                  DeprecationWarning, 2)
    if type(a) is int is type(b):
        if (b or a) < 0:
            return -math.gcd(a, b)
        return math.gcd(a, b)
    return _gcd(a, b)

def gcd(*a):
    """Return the greatest common divisor for 2 or more numbers"""
    if len(a) < 2:
        raise TypeError('gcd() takes at least 2 arguments')

    for i in a:
        if not math.isfinite(i):
            raise TypeError('Parameter Error!')

    b = math.gcd(a[0], a[1])
    for i in range(2, len(a)):
        b = math.gcd(b, a[i])

    return b

def multiplicativeKeyCount(alphabetLength, keepList=True):
    """Given a length of some alphabet, calculate how many valid multiplicative cipher keys that alphabet can have.

    Args:
        alphabetLength - The length of the alphabet
        keepList - Whether or not to actually keep track of the list of keys

    Returns:
        A tuple of the key count and the array of key values.  The second value is None if keepList is False.

    """
    keyCount = 0
    keyList = []
    # Start at 2 because 1 and 0 are never valid keys
    for i in range(2, alphabetLength):
        # Inrease the key count if the gcd of the two numbers is one.
        if gcd(i, alphabetLength) == 1:
            keyCount += 1
            # Add to the list of keys if we're keeping track of that
            if keepList:
                keyList.append(i)

    if keepList:
        return keyCount, keyList
    else:
        return keyCount, None

def main():
    # any primitive right triangle can be generated by n^2 - m^2, 2 nm, n^2 + m^2
    # Proof that this construction works
    """
    (n^2 - m^2)^2 + (2nm)^2
    n^4 - 2n^2 m^2 + m^4 + 4n^2 m^2
    n^4 + 2n^2 m^2 + m^4
    (n^2 + m^2)^2
    """

    MAXL = 1500000

    c = Counter()
    m = 1

    while perim(m + 1, m) <= MAXL:
        n = m + 1

        while perim(n, m) <= MAXL:
            if (n + m) % 2 == 0 or gcd(n, m) != 1:
                n += 1
                continue

            d = 1

            while d * perim(n, m) <= MAXL:
                c[d * perim(n, m)] += 1
                d += 1

            n += 1

        m += 1

    print(sum(1 for x in c if c[x] == 1))

def normalize(list):
    if len(list) < 2:
        return list
    g = list[0]
    for n in list[1:]:
        g = gcd(g, n)
    return [n // g for n in list]

def p329(squares=500,croakString='PPPPNNPPPNPPNPN'):
    
    t=time.clock()
    
    probs=0
    croakseq=[pn=='P' for pn in croakString] 
    croaks=len(croakseq)
    primes=primeSieve(squares)

    for start in range (1,squares+1):
        
        for seq in it.product([1,-1],repeat=croaks-1):
            positions=[start]+[0]*(croaks-1)
            for j in range(len(seq)):
                if positions[j]+seq[j]>squares:
                    positions[j+1]=squares-1
                elif positions[j]+seq[j]<1:
                    positions[j+1]=2
                else:
                    positions[j+1]=positions[j]+seq[j]        
            matches=sum([primes[positions[k]] == croakseq[k] for k in range(len(croakseq))])
            probs+=2**matches
            
    denom=squares*2**(len(croakseq)-1)*3**len(croakseq)
    gcd= math.gcd(probs,denom)
    
    print( str(probs//gcd)+"/"+str(denom//gcd))

    print(time.clock()-t)

def p127(limit):
    
    t=time.clock()
    rads=rsieve(limit+1)
    count=0
    csum=0    
    for c in range(1,limit):
        crads=rads[:c+1]
        crad=crads[c,1]
        radpair=crads[crads[:,1]<c/crad]
        if not c%2:
            radpair=radpair[radpair[:,0]%2==1]
        if len(radpair)<2:
            continue
        for i in range(len(radpair)):
            a=radpair[i]
            b=c-a[0]
            if b<a[0]:
                break                    
            brad=rads[b,1]
            if a[1]*brad*crad>=c:
                continue
            if math.gcd(a[0],b)>1:
                continue
            if b not in radpair[:,0]:
                continue
            csum+=c
            count+=1
            print((a[0],b,c),(a[1],rads[b][1],rads[c][1]))
    print(count,csum)    
    print(time.clock()-t)

def count_fractions_in_range(bottom, top, limit):
    """
    Counts the number of irreducible fractions n/d for
    all 1 ≤ d ≤ limit and n ≤ d between bottom and top,
    where bottom and top are fractions.
    """
    count = 0
    for d in range(1, limit + 1):
        # Find first fraction n/d > bottom.
        m = bottom.numerator * d
        if m % bottom.denominator == 0:
            n = int(m / bottom.denominator) + 1
        else:
            n = int(m / bottom.denominator + 1.0)

        # Find last fraction n/d < top
        y = top.numerator * d
        if y % top.denominator  == 0:
            z = int(y / top.denominator) - 1
        else:
            z = int(y / top.denominator)


        for i in range(n, z + 1):
            if gcd(i, d) == 1:
                count += 1

    return count

def gcd_multiple(numbers):
    l = len(numbers)
    if l == 1:
        return numbers[0]
    else:
        s = l // 2
        return gcd(gcd_multiple(numbers[:s]), gcd_multiple(numbers[s:]))