# your code goes here
p2=[]
p3=[]
p5=[]
p7=[]
p11=[]

inf=10**18

def pre():
	i=1
	while i<=inf:
		p2.append(i)
		i*=2
	i=1
	while i<=inf:
		p3.append(i)
		i*=3
	i=1
	while i<=inf:
		p5.append(i)
		i*=5
	i=1
	while i<=inf:
		p7.append(i)
		i*=7
	i=1
	while i<=inf:
		p11.append(i)
		i*=11
	
def cnt(n, k):
	ans=0
	if k==2:
		for i in range(1, len(p2)):
			if p2[i]>n:
				return ans
			ans+=1
	if k==3:
		for i in range(len(p2)):
			if p2[i]>n:
				return ans
			for j in range(1, len(p3)):
				if p2[i]*p3[j]>n:
					break
				ans+=1
	if k==5:
		for i in range(len(p2)):
			if p2[i]>n:
				return ans
			for j in range(len(p3)):
				if p2[i]*p3[j]>n:
					break
				for l in range(1, len(p5)):
					if p2[i]*p3[j]*p5[l]>n:
						break
					ans+=1
	if k==7:
		for i in range(len(p2)):
			if p2[i]>n:
				return ans
			for j in range(len(p3)):
				if p2[i]*p3[j]>n:
					break
				for l in range(len(p5)):
					if p2[i]*p3[j]*p5[l]>n:
						break
					for m in range(1, len(p7)):
						if p2[i]*p3[j]*p5[l]*p7[m]>n:
							break
						ans+=1
	if k==11:
		for i in range(len(p2)):
			if p2[i]>n:
				return ans
			for j in range(len(p3)):
				if p2[i]*p3[j]>n:
					break
				for l in range(len(p5)):
					if p2[i]*p3[j]*p5[l]>n:
						break
					for m in range(len(p7)):
						if p2[i]*p3[j]*p5[l]*p7[m]>n:
							break
						for p in range(1,len(p11)):
							if p2[i]*p3[j]*p5[l]*p7[m]*p11[p]>n:
								break
							ans+=1

def bin(lo, n, k, z):
	hi=inf
	while lo<hi:
		mid=(lo+hi)/2
		r=cnt(mid, k)
		if r-z>=n:
			hi=mid
		else:
			lo=mid+1
	return lo

pre()
t=int(raw_input())
while t:
	t=t-1
	s=raw_input().split()
	a=int(s[0])
	k=int(s[1])
	n=int(s[2])
	z=cnt(a-1, k)
	res=bin(a, n, k, z)
	print res