Problema C

Em Busca dos Números Perdidos

O famoso arqueólogo Carlos Pedregulho descobriu alguns artefactos de uma civilização antiga. Tendo em conta a sua investigação, ele pensa que estes artefactos pertenciam aos Primérios, um povo que já tinha conhecimentos de matemática e que em particular venerava os números primos como se fossem uma entidade divina (daí o nome com que ficaram conhecidos).

Durante as escavações, foram também descobertas um série de portas que protegem compartimentos secretos, que podem ter valores incalculáveis! As portas estão protegidas cada uma por dois códigos. Carlos tentou arrombá-las com tudo o que tinha disponível, mas não conseguiu. A única alternativa seria conseguir descobrir os tão preciosos códigos.

Um dia, entre os muitos artefactos descobertos, estavam uns papiros que Carlos pensa terem descritos os códigos para abrir as portas. Basicamente, um código é um número com um máximo de 4 dígitos. Depois de muito estudo, Carlos conseguiu perceber que os Primérios já usavam o sistema decimal, decifrando também os símbolos usados. O único problema é que certos símbolos foram parcialmente apagados pelo tempo, nao sendo agora legíveis. Portanto, só parte dos códigos era legível, mas era sempre possível pelo menos perceber quantos dígitos tinham.

Carlos ficou desiludido, mas uma investigação mais aprofundada permitiu-lhe descobrir algo mais sobre os códigos. Os Primérios já conheciam a soma e só escolhiam como códigos para uma porta números cuja soma desse um número primo! Eles acreditavam que isso lhes iria trazer os favores dos Deuses.

Carlos decidiu logo aproveitar essa descoberta para tentar abrir as portas. Pensou que sabendo que a soma é prima, e olhando para os números parciais, conseguiria descobrir os números. Contudo, mal começou a trabalhar nos primeiros códigos reparou que mesmo assim ainda existiam muitas hipóteses possíveis de completar os números de modo darem origem a um número primo.

Se o Carlos conseguisse saber exactamente de quantas maneiras diferentes se podem completar os números correctamente, poderia começar por experimentar os códigos com menor quantidade de maneiras, para finalmente abrir uma porta e começar a desvendar o segredo que ela escondia. Será que o pode ajudar?

Tarefa

A sua tarefa é escrever um programa para ajudar Carlos, dizendo de quantas maneiras diferentes se podem completar dois números parcialmente preenchidos de modo a que a sua soma dê um número primo.

Recorde que um número primo é um número inteiro positivo maior do que 1 sem nenhum divisor para além de 1 e o próprio número

Por exemplo, imagine que o papiro apresenta os códigos "12" e "3?" (onde ? representa um dígito ilegível). Existem neste caso precisamente duas maneiras possíveis de completar os números de modo a formarem um código válido: dizer que o dígito ilegível é 1 (12+31=43 que é um número primo) ou 5 (12+35=47 que é também um número primo).

Já se os códigos fossem "?1" e "?3" não existiria nenhuma maneira de completar os números (e portanto, nesse caso, Carlos podia ignorar os códigos).

Para efeitos de contagem, a ordem dos números importa. Por exemplo, se os códigos forem "??" e "??", 12 31 e 31 12 representam duas maneiras diferentes de se preencher os números (entre muitas outras possibilidades).

Outra coisa que deve ser notada é que podem existir zeros à esquerda. Por exemplo, para os códigos "?3" e "?", 03 0 é uma possibilidade correcta.

Dados

Um único input pode conter vários casos para testar. A primeira linha do standard input contém um número inteiroC (1≤C≤100), que representa precisamente o número de casos a testar.

Seguem-se C linhas, cada uma representando um caso para analisar, sendo que cada linha contém dois números parcialmente definidos, separados por um espaço. Um número parcialmente definido é representando por uma sequência de digitos e pontos de interrogação, onde estes últimos representam um digito ilegivel. Por exemplo, "?13?" representa um número de 4 dígitos, onde já sabemos o 2º e 3º digitos mas os outros dois estão ilegíveis.

Note que um número parcialmente definido só pode conter, no máximo, 4 dígitos e que podem existir número completamente legíveis, ou seja, sem nenhum ponto de interrogação.

Resultados

O output deve ter uma linha para cada caso de input no formato:

Caso #NUM_CASO (NUM1 e NUM2): MANEIRAS

onde NUM_CASO é o número do caso numerado sequencialmente a partir de 1, NUM1 e NUM2 são os números do input e MANEIRAS é o número diferente de maneiras de completar os números de modo a que a sua soma dê um número primo.

Note que podem existir casos onde não existe nenhuma maneira de preencher os números correctamente.

Exemplo de ficheiro de dados

7
12 3?
?1 ?3
12 24
12 25
?? ??
? 4?2
22 ?

Exemplo de ficheiros de resultados

Caso #1 (12 e 3?): 2
Caso #2 (?1 e ?3): 0
Caso #3 (12 e 24): 0
Caso #4 (12 e 25): 1
Caso #5 (?? e ??): 2097
Caso #6 (? e 4?2): 16
Caso #7 (22 e ?): 3