Problem: Darshak (Dark) was learning about numerals in words and he came across representation of "6743294" as shown below
.tg  {border-collapse:collapse;border-spacing:0;}
.tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}
.tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}

Ten Lakhs
Lakhs
Ten-Thousands
Thousands
Hundreds
Tens
Units
6
7
4
3
2
9
4
This can be extended to very high numbers like crores, ten crores and so on...

He learned two concepts.

1) Face Value:

The Face value of a digit in a numeral is its own value, at whatever place it may be.
eg: Face Value of 6 is 6 (as per above example) let say it is stored in 'f'

2) Place Value:

In a given numeral, 

Place value of unit digit = (unit digit * 1)

Place value of tens digit = (tens digit *10)

and so on,...

eg: place value of '4' at unit place is  4 * 1 = 4.

As always Dark is eager and wants you to find the place value of given digit and count the number of zero's present in it say let it be 'p' 

But, if the value of p comes out to be even number then we need to print the fth prime number or if it comes out to be odd then print the pth prime number. 

Note: Prime numbers start from 2.

Input:

First line contains t number of test case. Each next line contains one numeral say 'n' , 'm' the digit whose place value is to be obtained and 'x' position of the digit from units place towards the higher places.

Note: 
In an example, "6343"  if x=2 then it represents the "thousandth place" and if x=1 then "units place".we have considered digit as 3

Output:

Print the prime number as explained above.

Constraints:

1 ≤ t ≤ 1000
0 ≤ m ≤ 9 
1 ≤ x ≤ 100
1 ≤ n ≤ 10^101

Note:

1) Face value of zero is zero therefore the fth prime number i.e 0th prime number can be considered as 1.

2) Prime number starts from 2.

3)  No leading zeroes in the numeral.

Author : Darshak Mehta

SAMPLE INPUT
3
1005 0 2
7347 3 1
7777 7 4

SAMPLE OUTPUT
1
5
5

Solution (in PYTHON):

Solution:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def isprime(a):
	i=2
	while i*i<=a:
		if a%i==0:
			return False
		i+=1
	return True
primes=[1]
cnt=0
i=2
while cnt<=99:
	if isprime(i):
		primes.append(i)
		cnt+=1
	i+=1

t=int(raw_input())
while t:
	m=map(str,raw_input().split())
	f=int(m[1])
	n=len(m[0])
	x=int(m[2])
	i=n-1
	cnt=0
	while i>=0:
		if m[0][i]==m[1]:
			cnt+=1
		i-=1
		if x==cnt:
			break
	p=n-2-i
	if p%2:
		print primes[p]
	else:
		print primes[f]
	t-=1