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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
t = int(input())
while t > 0:
	a = int(input())
	b = int(input())
	l = int(input())
	x = 0
	y = 0
	z = 0
	a1 = 0
	b1 = 0
	c1 = 0
	while a // 10 != 0 or a % 10 != 0:
		a1 += (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
		x += 1
		a //= 10000000000
	while b // 10 != 0 or b % 10 != 0:
		b1 += (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
		y += 1
		b //= 10000000000
	c = a1 // b1 % 7 ** l
	while z < l:
		c1 += (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)
		c //= 282475249
		z += 10
	print(c1)
	t -= 1