tritzi

Tritzi

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

Poveste si cerinta...

Un trit este o unitate logica care poate lua $3$ valori: $0$, $1$ si $2$. Tritzii se pot folosi exact la fel ca si bitzii (despre care, probabil, ati auzit cu totzii). De exemplu, se pot transmite informatzii reprezentate sub forma unor siruri de tritzi. Pentru a nu se confunda cu sirurile de bitzi, sirurile de tritzi au o proprietate speciala : doi tritzi avand valorile $0$ si respectiv $1$ nu pot fi transmisi unul dupa altul. Astfel, exista siruri de tritzi valide si invalide (care contzin cel putzin o pereche de tritzi alaturatzi egali cu $0$ si $1$). De exemplu, sirul $02212212000211$ este un sir valid, dar sirurile $0122212$ sau $2221022$ nu sunt valide.
 
Determinati numarul de siruri de tritzi valide, de lungime $N$. Intrucat acest numar poate fi foarte mare, ne intereseaza numai valoarea acestuia modulo un numar $P$.

h2. Date de intrare

...

Pe prima linie a fisierului de intrare $tritzi.in$ se afla numarul intreg $T$, reprezentand numarul de teste ce urmeaza. Urmatoarele $T$ linii contzin cate $2$ numere intregi: $N$ si $P$.

h2. Date de iesire

...

Pentru fiecare test din fisierul de intrare veti afisa in fisierul de iesire $tritzi.out$ un numar reprezentand valoarea ceruta.

h2. Restrictii

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

* $1 ≤ T ≤ 30$
* $1 ≤ N ≤ 1 000 000 000$
* $1 ≤ P ≤ 32 000$

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

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

|4
1 997
4 997
21 997
999999999 13
|3
41
22
5

|

h3. Explicatie
 
...

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

2353