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ța

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 îndeplinesc 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 de intrare 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 de ieșire avid.out va conține un singur număr, reprezentând răspunsul pentru întrebarea dată, C.

Restricții și precizări

• 1 ≤ C ≤ 2
• 3 ≤ n ≤ 1.000.000
• 2 ≤ p ≤ 100
• 1 ≤ ai ≤ 5.000.000, unde ai 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ă.
• Pentru 12 puncte, C = 1, n ≤ 1000
• Pentru 17 puncte, C = 1, 1000 < n ≤ 1.000.000
• Pentru 29 puncte, C = 2, n ≤ 1000
• Pentru 42 puncte, C = 2, 1000 < n ≤ 1.000.000

Exemplul 1:

avid.in

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

avid.out

6

Explicație

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.

Exemplul 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.