== include(page="template/taskheader" task_id="primesato") ==

Poveste şi cerinţă...

Primesato este complet obsedata de numerele prime, si astfel a creat urmatoarea problema: se dau trei numere $N$, $M$ si $K$. Cate secvente $S$ de $N$ numere intregi intre $1$ si $K$ exista astfel incat toate subsecventele de lungime prima a lui $S$ au suma para? Raspunsul se cere modulo $M$.

h2. Date de intrare

Fişierul de intrare $primesato.in$ ...

Fişierul de intrare $primesato.in$ va contine, pe primul rand, numarul $T$ de teste din fisier
Pe urmatoarele $T$ randuri vor aparea descrierile celor $T$ teste, adica numerele $N, M, K$, cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $primesato.out$ ...

În fişierul de ieşire $primesato.out$ vor aparea cate $T$ randuri, fiecare cu raspunsul pentru cate un test, in ordine.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 100.000$
* $1 ≤ N, K ≤ 10^18^$
* $1 ≤ M ≤ 10^9^$

h2. Exemplu
table(example). |_. primesato.in |_. primesato.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
3 100 2
23 23 23
14343 23512 43646
| 1
11
6111

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="primesato") ==