ex = 10
mod = 7**ex
einv = 7**(ex-1)*6-1

def inv(a):
    return pow(a, einv, mod)

def digits(a):
    for v in a:
        for i in xrange(ex):
            v, d = divmod(v, 7)
            yield d

def convert(s):
    return [int(s[i:i+ex][::-1], 7) for i in xrange(0,len(s),ex)]

def deconvert(a,l):
    d = digits(a)
    return ''.join(str(d.next()) for i in xrange(l))

def solve():
    # take input
    a = raw_input()[::-1]
    b = raw_input()[::-1]
    l = input()

    # trim zeroes and convert to base 7^ex
    idx = 0
    while b[idx] == '0': idx += 1
    a = convert(a[idx:])
    b = convert(b[idx:])

    # extend a and b conveniently
    nl = l / ex + 1
    a += [0]*(nl-len(a))
    b += [0]

    # compute first few bits of quotient
    mul = inv(b[0])
    for i in xrange(nl):
        q = a[i] * mul % mod
        carry = 0
        ij = i
        for j in xrange(min(len(b), nl - i)):
            carry, sub = divmod(b[j] * q + carry, mod)
            a[ij] -= sub
            if a[ij] < 0:
                a[ij] += mod
                a[ij + 1] -= 1
            ij += 1
        a[i] = q

    # convert to string, and cleanup
    print deconvert(a, l).rstrip('0')[::-1] or '0'


if __name__ == '__main__':
    for cas in xrange(input()):
        solve()