Problema C - Para o Infinito e Mais Além

Buzz Lightyear é um intrépido astronauta sempre pronto a explorar todo o universo em busca da fortaleza secreta de Zurg, o seu arqui-inimigo. Agora, num novo planeta que encontrou, uma enigmática porta apresentava uma matriz quadrada preenchidas com digítos, um conjunto de números e o seguinte poema:

"Para esta porta abrir
Os números terás de contar
De quantas maneiras diferentes
Os podemos formar?"
Buzz percebeu que tinha de contar de quantas maneiras diferentes cada número podia ser formado ao percorrer um caminho na matriz para poder abrir a porta. A matriz que estava na porta era:
1 2 3
4 5 2
4 4 5
Depois de muito tentar o Buzz percebeu que os caminhos válidos na matriz passavam por começar em qualquer sítio e depois andar sucessivamente para a esquerda, para direita, para cima ou para baixo, sendo permitido passar várias vezes pela mesma casa, mas sendo necessário de cada vez mover-se numa das direcções. Por exemplo, o número 54 pode ser obtido de 3 maneiras diferentes, começando no número a azul e terminando no número a vermelho:
1 2 3      1 2 3      1 2 3
4 5 2      4 5 2      4 5 2
4 4 5      4 4 5      4 4 5
Já o número 44 pode ser encontrado de 4 maneiras diferentes:
1 2 3      1 2 3      1 2 3      1 2 3
4 5 2      4 5 2      4 5 2      4 5 2
4 4 5      4 4 5      4 4 5      4 4 5
Se o número fosse o 454 já existiriam 5 maneiras diferentes (com o verde a indicar uma casa onde se inicia e termina o caminho):
1 2 3      1 2 3      1 2 3      1 2 3      1 2 3
4 5 2      4 5 2      4 5 2      4 5 2      4 5 2
4 4 5      4 4 5      4 4 5      4 4 5      4 4 5
Com isto, Buzz conseguiu abrir a porta, mas deparou-se com... outra porta, também com uma matriz de dígitos e um conjunto de números! Será que podes ajudá-lo a abrir todas as portas com que se irá deparar?

O Problema

Dada uma matriz quadrada de dígitos de dígitos e um conjunto de números, a tua tarefa é descobrir de quantas maneiras diferentes cada número se pode formar na matriz. Um número pode formar-se começando em qualquer ponto da matriz e andando sucessivamente para a esquerda, direita, cima ou baixo, sendo permitido voltar a passar por um mesmo ponto da matriz.

Input

Na primeira linha do input vem um número inteiro T indicando o tamanho da matriz quadrada. Seguem-se exactamente T linhas, cada uma contendo exactamente T dígitos (de 0 a 9), separados por um espaço, indicando o conteúdo da matriz.

A seguir vem uma linha com um único número inteiro Q indicando a quantidade de números a considerar. Seguem-se exactamente Q linhas, cada uma contendo um único número inteiro Ni, indicando o i-ésimo número a considerar para contagem na matriz.

Output

O output deve ter exactamente Q linhas. Em cada uma delas deve ser imprimido um único número inteiro Mi indicando de a quantidade de maneiras diferentes de formar o número Ni na matriz dada. Estas quantidades devem vir pela mesma ordem em que os números aparecem no input.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ T ≤ 500       Tamanho da matriz
1 ≤ Q ≤ 5       Quantidade de números a considerar
1 ≤ Ni ≤ 1 000 000       Números a considerar
1 ≤ Mi ≤ 2 000 000 000       De quantas formas diferentes se pode formar cada número

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 60% dos pontos, o tamanho da matriz é inferior ou igual a 10.

Exemplo de Input

3
1 2 3
4 5 2
4 4 5
3
44
54
454

Exemplo de Output

4
3
5

Qualificação para a final das ONI'2011
(12/05 a 14/05 de 2011)