def bton(b):
    """
    macht aus dem bytearray (bytes) b (256-System, 256-System, Typ bytes) eine int-Zahl
    """
    if len(b) == 1:
        return b[0]
    else:
        return b[-1] + 256*bton(b[:-1])

def ntob(n):
    """
    gibt zu einer int-Zahl n ein bytearray (256-System, big endian)
    zurueck, endrekursiv
    """
    def h(akku,a):
        if a < 256:
            return [a] + akku
        else:
            return h([a%256]+akku,a//256)
    return bytearray(h([],n))

def ggt(a,b):
    """
    berechnet iterativ den ggt von a und b
    """
    while b > 0:
        (a,b) = (b,a%b)
    return a

def ggtr(a,b):
    """
    berechnet rekursiv den ggt von a und b
    """
    if b == 0:
        return a
    else:
        return ggtr(b,a%b)

def eggt(a,b):
    """
    gibt für a,b >= 0 ein Tripel (g,x,y) zurueck, für das gilt  ax + by = g = ggT(a,b)
    """
    if b == 0:
        return (a,1,0)
    else:
        # print(a,'=',a//b,'*',b,'+',a%b) # DEBUG
        (g,x,y) = eggt(b,a%b)
        # print(g,y,x -(a//b)*y) # DEBUG
        return (g,y,x -(a//b)*y)

def modinv(a, m):
    """
    gibt das modulare Inverse zu a und dem Modul m zurück
    """
    g, x, y = eggt(a, m)
    if g != 1:
        return None
    else:
        return x % m

import math
import functools
import operator

def primfaktoren(n):
    """
    die Primfaktoren von n werden als Liste zurückgegeben
    """
    # m = n
    f = []
    while n%2 == 0:
        f = f + [2]
        n = n//2
    while n%3 == 0:
        f = f + [3]
        n = n//3
    t = 5
    diff = 2
    w = round(math.sqrt(n))
    while t <= w:
        while n%t == 0:
            f = f + [t]
            n = n//t
        t = t + diff
        diff = 6 - diff
    if n > 1:
        f = f + [n]
    # assert functools.reduce(operator.mul,f,1) == m
    return f