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

t =input()
cas=1
while t>0:
	x, p=raw_input().split()
	x=int(x)
	p=str(p)
	l=len(p)
	q=1
	cnt=0;
	while True:
		s=str(q)
		if len(s)>=l:
			s=s[:l]
			if (p==s):
				print "Case " + str(cas) + ": " + str(cnt)
				break
		q=q*x
		cnt=cnt+1
	t=t-1
	cas=cas+1