from collections import Counter
from math import gcd, prod

def factor(m):
    n = m
    f = []
    for d in [2, 3, 5]:
        while n % d == 0:
            f.append(d)
            n //= d
    inc = (4, 2, 4, 2, 4, 6, 2, 6)
    i, d = 0, 7
    while d * d <= n:
        while n % d == 0:
            n //= d
            f.append(d)

        d += inc[i]
        i = (i + 1) % 8
    if n > 1:
        f.append(n)
    cnt = Counter(f)

    return cnt


def legendre(n, p):
    m = n
    s = 0
    while m > 0:
        s += m // p
        m //= p
    return s

def products(p, pa):
    T = [1] * (pa + 1)
    for j in range(1, pa + 1):
        if j % p != 0 :
            T[j] = (T[j - 1] * j) % pa
        else:
            T[j] = T[j - 1]
    return T
    
def chinese_remainder_theorem(fs, rs):
    n = prod(fs)
    s = 0
    for f, r in zip(fs, rs):
        m = n // f
        inv = pow(n // f, -1, f)
        s += r * inv * m
    return s % n

def fact_no_p(n, p, pa, T, W):
    if n == 0:
        return 1
    q, r = divmod(n, pa)
    fp = (pow(W, q, pa) * T[r]) % pa
    return (fp * fact_no_p(n // p, p, pa, T, W)) % pa

tests = (((7, 10), 4), ((13, 8), 6), ((5, 3), 1), ((29, 36), 12))

def last_digit(n, b):
    cnt = factor(b)
    es = {}
    m = float('inf')
    for p, exp in cnt.items():
        e = legendre(n, p)
        es[p] = e
        m = min(m, e // exp)

    fs, rs = [], []
    for p, a in cnt.items():
        pa  = p ** a
        bi  = b // pa        
        ei  = es[p]
        delta = ei - m * a

        T = products(p, pa)
        W = T[pa]

        A   = fact_no_p(n, p, pa, T, W) % pa        
        inv = 1 if m == 0 else pow(bi, -m, pa)  
        fs.append(pa)
        r = (pow(p, delta, pa) * A * inv) % pa
        rs.append(r)
    crt = chinese_remainder_theorem(fs, rs) 
    return crt

for (n, b), res in tests:
    r = last_digit(n, b)
    print("r :", r, res)