secvente

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 $p^y$ ($y \in ℕ$, $y \neq 0$) sau $q \cdot p^m$, $m \in ℕ$ și $q$ un număr prim, numindu-le numere $p$-prime. De exemplu, numerele $2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17$sunt primele $14$ numere $2$-prime deoarece $2 = 2^1$, $3 = 3 \cdot 2^0$, $4 = 2^2$, $5 = 5 \cdot 2^0$, $6 = 3 \cdot 2^1$, $7 = 7 \cdot 2^0$, $8 = 2^3$, $10 = 5 \cdot 2^1$, $11 = 11 \cdot 2^0$, $12 = 3 \cdot 2^2$, $13 = 13 \cdot 2^0$, $14 = 7 \cdot 2^1$, $16 = 2^4$, $17 = 17 \cdot 2^0$.

Î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 $a_1, a_2, a_3, \dots, a_n$, 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

Pe prima linie a fișierului secvente.in se află 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 $a_1, a_2, a_3, \dots, a_n$, numerele din șirul Mariei.

Date de ieșire

Fișierul secvente.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 \leq D \leq 15$;
• $1 \leq k, n \leq 15 \ 000$;
• $2 \leq p \leq 30 \ 000$; $p$ este un număr natural prim
• $1 \leq a_1, a_2, a_3, \dots, a_n \leq 30 \ 000$; $a_1, a_2, a_3, \dots, a_n \in ℕ$
• 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

secvente.in

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

secvente.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:
$a_1 = 7$ (număr prim), $a_2 = 27 = 3^3$ (putere a lui $3$) și $a_4 = 45$ = $5 \cdot 3^2$ (număr prim înmulțit cu o putere a lui $3$).

În șir sunt două secvențe cu câte doua numere $3$-prime: $a_1, a_2$ respectiv $a_2, a_3, a_4$.
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$.