4
39 20
183 11
551 27
85 16 8
4 65
5 12
7 24
9 38
12 24
14 10
65 75
31 26
Case 1: 9
Case 2: 4
Case 3: 6
Case 4: 11
 Case 1: 8
Case 2: 3
Case 3: 4
Case 4: 9
Case 5: 5
Case 6: 7
Case 7: 6
Case 8: 9

for i in range(input()):
	x, y =raw_input().split()
	x=int(x)
	t=x
	e=2
	x=x**e
	while True:
		if str(x).startswith(y):
			#print x,y,e
			print "Case {}: {}".format(i+1, e)
			break
		e+=1
		x*=t