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

Difficulty: interview

Starter code:

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