Secvențe cu divizori cu impare și cu toate chestiile de pe pământ

Naaaaaaah, cred ca e ggs

Cerință

Se dă $N$, $K$ și un șir $a$ de $N$ numere întregi. Să se afle câte secvențe contigue din $a$ (adică formate din numere de pe poziții consecutive în șir), au proprietatea că cel puțin $K$ dintre numerele din această secvență sunt speciale.

Definim un număr ca fiind special dacă are cel puțin un divizor diferit de $1$ care are doar cifre impare. De exemplu, $28$ este special, deoarece $28 \ \vdots \ 7$, $38$ este special, deoarece $38 \ \vdots \ 19$, însă $16$ nu este special.

Date de intrare

Pe prima linie se găsesc două numere întregi, $n$ și $k$. Pe următoarea linie se găsesc $n$ numere întregi, reprezentând șirul $a$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, reprezentând numărul căutat.

Restricții și precizări

• $1 \leq K \leq N \leq 100 \ 000$
• $1 \leq a_i \leq 1 \ 000 \ 000$ (pentru $i$ de la $1$ la $N$)
• Pentru $20$ de puncte, $N \leq 100$
• Pentru alte $20$ de puncte, $N \leq 3 \ 000$

Exemplu

stdin

5 2
9 46 93 15 2021

stdout

7

Explicație

Secvențele formate din cel puțin $K = 2$ numere speciale sunt:

1. $9, 46, 93$ ($9$ este special, deoarece $9 \ \vdots \ 3$, iar $93$ este special, deoarece $93 \ \vdots \ 31$);
2. $9, 46, 93, 15$ ($9$ este special, deoarece $9 \ \vdots \ 3$, iar $93$ este special, deoarece $93 \ \vdots \ 31$);
3. $9, 46, 93, 15, 2 \ 021$ ($9$ este special, deoarece $9 \ \vdots \ 3$, iar $93$ este special, deoarece $93 \ \vdots \ 31$);
4. $46, 93, 15$ ($93$ este special, deoarece $93 \ \vdots \ 31$, iar $15$ este special, deoarece $15 \ \vdots \ 5$);
5. $46, 93, 15, 2 \ 021$ ($93$ este special, deoarece $93 \ \vdots \ 31$, iar $15$ este special, deoarece $15 \ \vdots \ 5$);
6. $93, 15$ ($93$ este special, deoarece $93 \ \vdots \ 31$, iar $15$ este special, deoarece $15 \ \vdots \ 5$);
7. $93, 15, 2 \ 021$ ($93$ este special, deoarece $93 \ \vdots \ 31$, iar $15$ este special, deoarece $15 \ \vdots \ 5$).