Problema A - Alice no País dos Primos

Enquanto passeava no jardim, Alice viu um coelho branco de colete que carregava um relógio de bolso. Surpreendida por esta visão, decidiu seguir o coelho, mas acabou por cair na sua toca, que era muito funda. Ao chegar ao chão, deparou-se com três números em acesa discussão: o dois (2), o três (3) e o cinco (5). Mais à frente viu uma compridíssima procissão de números. Com a sua mente curiosa, reparou que os números da procissão, bem como os números que discutiam entre si, eram todos números primos. Recorda que um número primo é um número inteiro maior que um que apenas é divisível por si próprio e por um. Por exemplo, os 10 primeiros números primos são:

2 3 5 7 11 13 17 19 23 29

A procissão de primos que Alice agora testemunhava era uma enorme sequência de números primos, todos uns atrás dos outros, que começava assim:

2 2 3 2 3 5 2 3 5 7 2 3 5 7 11 2 3 5 7 11 13 2 3 5 7 11 13 17 ...

Os números vinham por uma ordem específica que parecia um pouco estranha a princípio. Contudo, Alice conseguiu perceber o padrão que eles faziam! Seja S_n a sequência dos n primeiros primos. Por exemplo:

S1 -> 2
S2 -> 2 3 
S3 -> 2 3 5
S4 -> 2 3 5 7

A sequência da procissão era constituída pelos números da sequência S₁, seguidos pelos números da sequência S₂, seguidos pelos números da sequência S₃, seguidos pelos números da sequência S₄ e assim sucessivamente.

Foi nessa altura que o Rei e a Rainha dos números primos repararam na Alice. "Quem és tu ?", perguntaram eles. "O que fazes aqui, não sendo tu um número primo?", continuaram. Alice não sabia o que responder, de tão espantada que estava com tudo o que a rodeava. Foi então que a Rainha decidiu que a Alice tinha de provar que merecia estar ali. "Saberás tu, minha cara menina, dizer-me qual o milionésimo dígito da minha procissão?", perguntou a Rainha. Alice ficou muito pensativa e a Rainha explicou que para resolver este enigma tinha de pensar na procissão como uma sequência de dígitos que resulta da concatenação de todos os números da procissão. Assim, a procissão pode ser vista como a seguinte sequência de dígitos (que é igual à mostrada anteriormente mas com todos os números concatenados):

22323523572357112357111323571113172357111317...

O 1º dígito é 2, o 2º dígito é 2, o 3º dígito é 3 e por aí adiante. Por exemplo, o 16º dígito é 1. Mas e o milionésimo?

Alice pensou mais um pouco e quando estava quase a resolver a charada, a Rainha lembrou-se de um outro pormenor. É que por vezes os números, tal como o dois, o três e o cinco, ficam tão entretidos a discutirem uns com os outros que se esquecem da procissão. Nesse caso a procissão começa com o menor número primo P que não está a discutir e segue o mesmo tipo de padrão: S^P₁, S^P₂, S^P₃, ..., onde S^P_n é a sequência dos n primeiros primos a começar no número primo P. Por exemplo:

Para P=5 a sequencia é: 5575711571113571113175711131719...
Para P=11 a sequencia é: 111113111317111317191113171923...

Como descobrir neste caso o milionésimo dígito? E de forma mais geral ainda, conhecendo P, como descobrir o dígito de uma qualquer posição? Tens de ajudar a Alice, porque senão a Rainha irá prendê-la nas masmorras do país dos primos...

O Problema

Dado um número primo P e uma sequência de números Q_i, a tua tarefa é calcular, para cada Q_i, qual o dígito que ocupa a posição de ordem Q_i (ou seja, o Q_i-ésimo digito) na procissão de primos que começa com P. Recorda que a procissão pode ser pensada como uma sequência de dígitos formada pela concatenação de S^P₁, S^P₂, S^P₃, .... (e por aí adiante), onde S^P_n é a sequência dos n primeiros primos a começar no primo P.

Input

Na primeira linha do input vêm dois números inteiros, P e C, separados por um único espaço. P é um número primo que indica onde a sequência começa e C indica o número de casos que se seguem.

Seguem-se C linhas, cada uma contendo um único inteiro Q_i, indicando que a Rainha pretende saber qual o Q_i-ésimo dígito da procissão, tal como foi atrás descrita, supondo que começa com P.

Output

O output deve ser constituído por C linhas, cada uma indicando a resposta a um dos casos, na mesma ordem em que eles aparecem no input, ou seja, qual o dígito que aparece na posição de ordem Q_i (o Q_i-ésimo dígito da sequência, portanto).

Restrições

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

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 30% dos pontos, acontece sempre que P, C e Q_i são todos menores ou iguais a 100.

Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que os Q_i são menores ou iguais a 1 000 000.

Exemplo de Input 1

2 6
1
2
3
16
6
8

Exemplo de Output 1

2
2
3
1
5
3

Exemplo de Input 2

11 4
1
5
6
10

Exemplo de Output 2

1
1
3
3