Problema A - O Cartaz do Google

A foto aqui ao lado mostra o cartaz que há tempos a Google colocou numa concorrida auto-estrada, nos Estados Unidos. Quem descobrisse o primeiro número primo com 10 algarismos na dízima infinita do número e, base dos logaritmos naturais, deveria escrever num "bráuser" esse número, seguido de ".com" e iria parar a um sítio com mais instruções. Eventualmente, acabaria por ser convidado para uma entrevista, e, quem sabe, ganharia um belo emprego.

Não vão eles, na Google, arranjar outra charada do mesmo género, o melhor é treinarmo-nos nesta problemática dos números primos que aparecem em dízimas infinitas.

Concretamente, neste exercício, é-nos dada uma cadeia de algarismos, muito comprida, e queremos contar o número de ocorrências de números primos com x algarismos (para um x dado) nessa cadeia. Por exemplo, se a cadeia for "1297521973" e x valer 2, temos 5 ocorrências: 29, 97, 19, 97 (de novo) e 73.

O Problema

Dada uma cadeia de algarismos s e um número x, calcular o número de ocorrências de números primos formados por x algarismos consecutivos em s.

Input

Na primeira linha vem o número inteiro x, o comprimento em algarismos decimais dos números primos em que estamos interessados, 1 <= x <= 7. Seguem-se uma ou mais linhas não vazias (em número indeterminado) totalmente formadas por algarismos. Cada linha tem no máximo 100 algarismos. A cadeia s na qual queremos procurar os números primos é a que resulta da concatenação da sucessivas linhas. O comprimento máximo de s é 10000000.

Output

O output tem uma linha, na qual aparece um número: o número de ocorrências de números primos formados por x algarismos consecutivos na cadeia s.

Exemplo de Input 1

3
6748508573
9031663904

Exemplo de Output 1

2

Exemplo de Input 2

2
129
752
197
3

Exemplo de Output 2

5