We have an unsolved mystery this time too! 

Input:

First line of input contains T – the number of test cases. Each of the next T lines contain two integers a and b separated by a space.

Output:

Output T lines, each containing a single integer that is the output of that test case.

Constraints:

1 ≤ T ≤ 300

1 ≤ a ≤ 999

5 ≤ b ≤ 8

SAMPLE INPUT
6
5 5
10 6
2 7
90 6
5 6
2 8

SAMPLE OUTPUT
10
14
2
230
5
2

Explanation

No explanation!!
T = input()

for t in xrange(T):
	a,b = map(int,raw_input().split())
	if a < b:
		print a
		#break
	else:	
		V = []
		#C = a
		while a >= b:
			V.append(a%b)
			a = a/b
		V.append(a)
		V.reverse()
		S = map(str,V)
		print "".join(S)