Missing Digits

Thanks to Clive Fraser for creating this task!

In this problem you will be given several positive integers. Each of these will have one or more digits missing. The missing digits will be replaced by the '?' character. You are told that the original number is divisible by 13. From this information it is not possible to identify the missing digits uniquely but it is possible to find valid combinations. You are asked to find the number of ways in which these digits can be replaced so that the resulting number is divisible by 13. Note that the first digit of a number cannot be 0 (leading zeros are not allowed) so a '?' in the first position can only be replaced by any of the digits from 1 to 9. A '?' appearing at any other position can be replaced by any of the digits from 0 to 9.

Consider the number ?53?76. Here we have two missing digits. The first can be replaced in 9 different ways. The second can be replaced in 10 different ways. So there are 90 different ways of replacing the two digits. How many of these lead to the resulting number being divisible by 13? It is fairly simple to make each of the 90 replacements and to divide the result by 13. This shows that 6 of the numbers are divisible by 13. These are listed below.

1 453076 = 13 x 34852
2 553176 = 13 x 42552
3 653276 = 13 x 50252
4 753376 = 13 x 57952
5 853476 = 13 x 65652
6 953576 = 13 x 73352

The numbers in the actual problem are typically larger than this. No number will have more than 100 digits and no number will have more than 20 missing digits.

Input and Output: The first line of the problem will be a single integer N denoting the number of test cases. Each test case will consist of a single string representing a positive integer with several missing digits. For each test case you must find the number of ways in which these digits can be replaced so that the resulting number is divisible by 13. Give these answers, separated by spaces, as a single string.

Example:

input:
5
?8207
?53?76
45928?33?7
5?61560045?17?3
4?687762??31?8041075

answer:
1 6 7 73 770