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

i=1
for _ in xrange(input()):
	a,b=map(int,raw_input().split())
	n=1
	x=1
	while True:
		x=x*a
		if str(b) == str(x)[:len(str(b))]:
			break
		n=n+1
	print "Case %d:"%i, n
	i+=1