Algorithmes et Structures de Données

Nombre de nombres premiers dans un intervalle

Étant donnés n nombres, il s’agit d’examiner toutes les sous-séquences contiguës de longueur k et de trouver celle qui contient le plus grand nombre de nombres premiers.

Entrée

La première ligne de l’entrée contient deux entiers n (1 ≤ n ≤ 50 000) et k (1 ≤ k ≤ n).

La ligne suivante contient n entiers a1,a2,...,ana_1, a_2, ..., a_n (1 ≤ aia_i ≤ 10810^8).

Sortie

Le programme doit afficher le nombre maximal de nombres premiers dans une sous-séquence de longueur k.

Exemples

Input

Output

6 3
2 5 10 3 6 7

2

6 3
5 4 2 3 7 1

3

6 2
5 1 6 1 7 4

1

Constraints

Time limit: 8 seconds

Memory limit: 512 MB

Output limit: 1 MB