Mariei îi plac numerele prime şi puterile numerelor prime. Pornind de la un număr prim p, ea construieşte noi numere, fiecare număr construit fiind un produs de forma py (y număr natural nenul) sau q∙pm, m număr natural şi q un număr prim, numindu-le numere p-prime. De exemplu, numerele 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 16, 17 sunt primele 13 numere 2-prime deoarece 2=21, 3=3•20, 4=22, 5=5•20, 6=3•21, 7=7•20, 8=23, 10=5•21, 12=3•22, 13=13•20, 14=7•21, 16=24, 17=17•20.

Într-o zi Maria a găsit o foaie de hârtie, pe care era scris un şir format din n numere naturale nenule.

Cum pe lângă numerele p-prime ea este pasionată şi de secvenţe, şi-a pus următoarea întrebare: câte secvenţe sunt pe foaie cu următoarele proprietăţi:

• conţin exact k numere p-prime;
• încep şi se termină cu un număr p-prim.

În plus, Maria doreşte să ştie care este poziţia de început şi cea de final, pentru fiecare secvenţă descoperită, relative la şirul scris pe foaia de hârtie.

Cerinţă

Scrieţi un program care să citească mai multe seturi de date, fiecare set fiind format din numerele n, p, k, cu semnificaţiile din enunţ, şi şirul cu n elemente a1, a2, a3, … an, numerele Mariei. Programul va determina pentru fiecare set de date numărul secvenţelor ce conţin exact k numere p-prime, precum şi poziţiile de început şi de final ale acestor secvenţe în şirul din set.

Date de intrare

Fișierul de intrare secvente2.in conține pe prima linie numărul D reprezentând numărul de seturi de date din fişier. Seturile de date sunt scrise în fişier pe linii succesive. Pentru fiecare set de date, prima linie conţine câte trei numere naturale: n (numărul de elemente de pe foaie), p şi k (cu semnificaţia din enunţ), separate prin câte un spaţiu, iar fiecare dintre următoarele n linii conţine câte un număr natural al şirului a1, a2, a3, … an, numerele din şirul Mariei.

Date de ieșire

Fișierul de ieșire secvente2.out va conține D soluţii corespunzătoare celor D seturi de date. Pentru fiecare soluţie prima linie va conţine un număr x reprezentând numărul de secvenţe ce îndeplinesc proprietăţile cerute, iar fiecare dintre următoarele x linii vor conţine câte 2 numere naturale, separate printr-un spaţiu, reprezentând poziţia de început, respectiv de final a fiecărei secvenţe, linii ordonate crescător după poziţia de început. Dacă în şir nu există o astfel de secvenţă, prima linie a setului va conţine valoarea 0.

Restricții și precizări

• 1 ≤ D ≤ 15;
• 1 ≤ k ≤ n ≤ 15000;
• 2 ≤ p ≤ 30000; p este un număr natural prim
• 1 ≤ a1, a2, a3, … an ≤ 30000; a1, a2, a3, … an sunt numere naturale nenule (poziţiile din şir sunt numerotate de la 1)
• numărul 1 nu este p-prim.
• o secvenţă dintr-un şir este formată din elemente aflate pe poziţii consecutive în şirul dat.

Exemplu:

secvente2.in

2
5 3 2
7
27 
4 
45 
1
3 5 7
3
4
5

secvente2.out

2
1 2
2 4
0

Explicație

Cum D=2, fişierul de intrare conţine două seturi de date.

Primul set de date: n=5, p=3, k=2 şi a=(7, 27, 4, 45, 1). Şirul din acest set conţine următoarele numere 3-prime: a1=7 (număr prim), a2=27=33 (putere a lui 3) şi a4=45=5*32 (număr prim înmulţit cu o putere a lui 3). În şir sunt două secvenţe cu câte 2 numere 3-prime: a1, a2 respectiv a2, a3, a4. Pe prima linie a fişierului de ieşire se va scrie valoarea 2, iar pe următoarele două linii, poziţiile de început şi de final ale celor două secvenţe determinate.

Şirul a din al doilea set de date, n=3, p=5, k=7, a=(3,4,5), nu conţine nici o secvenţă cu proprietatea cerută. Astfel, în fişierul de ieşire, pe cea de-a patra linie, se va scrie valoarea 0.