Our little chef is little dumb. So much dumb that when his crush gave him her number he forgets it. But since little dumbo chef is such a good friend of yours you decided to help him. Here is some vague memories of the number that chef can recall :

1.It is a palindrome.

2.It is a prime number.

3.It is of n digits ( 4

After digesting a memory enhancement pill he recalls (n-2) digits of the number. Now since the search criteria is so much narrowed, you are to write a program which prints number of possible candidates of the phone number of his crush.

A number is a successful candidate if :

1. It is prime and a palindrome.

2. It is of n digits.

3. Only deletion of two digits from the potential candidate makes it equal to the number which the chef has recalled.

Input

The first line of the input contains an integer T denoting the number of test cases, for each test case enter the number sequence recalled by chef of N - 2 digits and digits of original number i.e N

Output

For each test case, output a single line with number of phone numbers possible.

Constraints

• 4 = N = 11

Example

Input: 2 37343 7 57675 7 Output: 1 1

Explanation

Case 1 : 1 number is possible i.e 3743473

Case 2 : 1 number is possible i.e. 7576757