Description

We define a date as an 8-digit number. Digits $1 \sim 4$ form the year, digits $5 \sim 6$ form the month, and digits $7 \sim 8$ form the day. If a part has fewer digits, it is padded with $0$. Also, the day represented by the date must really exist, and the year ranges from $1 \sim 9999$.

All miracle dates share the same property: the 2-digit number formed by the “day”, the 4-digit number formed by “month + day”, and the 8-digit number formed by “year + month + day” are all prime numbers. However, not every date with this property will necessarily have a miracle.

Now you are given a date that may have a miracle, but unfortunately this date is incomplete: among the 8 digits, some digits may be unknown. You need to determine how many possible dates it could be, so that you can be fully prepared to welcome the miracle.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines each contain an 8-character string. If the $i$-th character is -, it means the $i$-th digit of the date is unknown; otherwise, it means the $i$-th digit of the date is the digit at position $i$ in the string.

Output Format

For each test case, output one integer per line, representing the answer.

2
53-7-3-7
20190629

6
0

Hint

[Sample $1$ Explanation]

The 6 possible dates for 53-7-3-7 are:

53070307
53070317
53170307
53370307
53570317
53770307

[Constraints]

There are $10$ test points in total. Let $c$ be the number of - characters in the 8-character string.

For the first $9$ test points, in the $i$-th test point it is guaranteed that $c = i - 1$.

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 10$.

Translated by ChatGPT 5