Sereja has two integers — A and B — in 7-ary system. He wants to calculate the number C, such that B * C = A. It is guaranteed that B is a divisor of A.

Please, help Sereja calculate the number C modulo 7L.

-----Input-----

First line of input contains an integer T — the number of test cases. T tests follow.

For each test case, the first line contains the integer A, and the second line contains the integer B, and the third line contains the integer L. A and B are given in 7-ary system.

-----Output-----
Output the answer in 7-ary system.

-----Constraints-----
- 1 ≤ T ≤ 10
- A and B are both positive integers.
- Length of A is a positive integer and doesn't exceed 106.
- L and length of B are positive integers and do not exceed 10000.

-----Subtasks-----
- Sub task #1 (20 points): Length of A is a positive integer and doesn't exceed 20.
- Sub task #2 (30 points): Length of A is a positive integer and doesn't exceed 2000.
- Sub task #3 (50 points): Original constraints.

-----Example-----
Input:3
21
5
10
202
13
1
202
13
2

Output:3
3
13

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't=int(input())\nwhile t>0 :\n\ta=int(input())\n\tb=int(input())\n\tl=int(input())\n\tx=0\n\ty=0\n\tz=0\n\ta1=0\n\tb1=0\n\tc1=0\n\twhile(a//10!=0 or a%10!=0):\n\t\ta1+=(a%10+((a//10)%10)*7+((a//100)%10)*49+((a//1000)%10)*343+((a//10000)%10)*2401+((a//100000)%10)*16807+((a//1000000)%10)*117649+((a//10000000)%10)*823543+((a//100000000)%10)*5764801+((a//1000000000)%10)*40353607)*(282475249**x)\n\t\tx+=1\n\t\ta//=10000000000\n \n\twhile (b//10!=0 or b%10!=0):\n\t\tb1+=(b%10+((b//10)%10)*7+((b//100)%10)*49+((b//1000)%10)*343+((b//10000)%10)*2401+((b//100000)%10)*16807+((b//1000000)%10)*117649+((b//10000000)%10)*823543+((b//100000000)%10)*5764801+((b//1000000000)%10)*40353607)*(282475249**y)\n\t\ty+=1\n\t\tb//=10000000000\n\tc=(a1//b1)%(7**l)\n\twhile z<l:\n\t\tc1+=(c%7+((c//7)%7)*10+((c//49)%7)*100+((c//343)%7)*1000+((c//2401)%7)*10000+((c//16807)%7)*100000+((c//117649)%7)*1000000+((c//823543)%7)*10000000+((c//5764801)%7)*100000000+((c//40353607)%7)*1000000000)*(10000000000**(z//10))\n\t\tc//=282475249\n\t\tz+=10\n\tprint(c1)\n\tt-=1'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13943