Avid

Alex este un băiat căruia îi place să citească și care contorizează cât de mult a citit pe parcursul ultimelor $n$ zile. Mai precis, el și-a notat câte pagini a citit în fiecare dintre acestea. Chiar dacă pasiunea lui este literatura, își dorește să progreseze și la informatică. Alex și-a pus două întrebări legate de șirul format din numărul de pagini citite de el în ultimele $n$ zile, dar după ce a petrecut câteva zile gândindu-se la ele și-a dat seama că sunt prea dificile pentru el. Ajutați-l să găsească răspunsurile!

Cerință

Fie numărul $n$, numărul $p$ și acel șir de valori notate de Alex în cele $n$ zile. Determinați răspunsul la următoarele întrebări care îl frământă pe Alex:

1. Câte triplete de numere aflate pe poziții consecutive în șirul dat îndeplines condiția ca cel mai mare divizor comun al lor să aibă cel mult $p$ divizori naturali?
2. Care este lungimea maximă a unei secvențe din șirul dat, în care cel mai mare divizor comun al oricărui triplet de numere situate pe poziții consecutive are cel mult $p$ divizori naturali?

Date de intrare

Fișierul avid.in conține pe prima linie un număr natural $C$, având valoarea $1$ sau $2$, reprezentând numărul întrebării. Pe a doua linie se află două numere naturale $n$ și $p$, în această ordine, cu semnificația din enunț. A treia linie din fișier conține $n$ numere naturale reprezentând șirul de valori notate în cele $n$ zile. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul avid.out va conține un singur număr, reprezentând răspunsul pentru întrebarea dată, $C$.

Restricții

• $1 \le C \le 2$
• $3 \le n \le 1 \ 000 \ 000$
• $2 \le p \le 100$
• $1 \le a_i \le 5 \ 000 \ 000$, unde $a_i$ este numărul de pagini citite de Alex în ziua $i$ (Alex citește la o viteză impresionantă)
• Pentru prima cerință, se garantează că există cel puțin un triplet cu proprietatea indicată.
• Pentru a doua cerință, se garantează că există cel puțin o secvență validă cu proprietatea indicată.

Exemplu 1

avid.in

1
10 3
12 48 36 6 3 7 12 16 24 3

avid.out

6

Explicație

$cmmdc(12, 48, 36) = 12$, care are $6$ divizori naturali.

$cmmdc(48, 36, 6) = 6$, care are $4$ divizori naturali.

$cmmdc(36, 6, 3) = 3$, care are $2$ divizori naturali.

$cmmdc(6, 3, 7) = 1$, care are $1$ divizor natural.

$cmmdc(3, 7, 12) = 1$, care are $1$ divizor natural.

$cmmdc(7, 12, 16) = 1$, care are $1$ divizor natural.

$cmmdc(12, 16, 24) = 4$, care are $3$ divizori naturali.

$cmmdc(16, 24, 3) = 1$, care are $1$ divizor natural.

Deci, $6$ dintre cele $8$ triplete au cel mult $p = 3$ divizori naturali.

Exemplu 2

avid.in

2
7 2
12 48 36 6 3 7 12

avid.out

5

Explicație

Pentru că $p = 2$, cea mai lungă secvență este $36, 6, 3, 7, 12$.