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

Gigel a fost invitat la aniversarea prietenei lui dragi, Alinuta, pe post de DJ. Principala lui problema este ca nu cunoaste decat $2$ melodii (prima dureaza $1$ minut, iar a doua $2$ minute), dar el a fost chemat pentru exact $N$ minute de reprezentatii. Deoarece Gigel este student la FMI si nu la Conservator nu il deranjeaza acest lucru, in plus este curios sa stie pentru un $N$ dat care este numarul de moduri de a dispune cele $2$ melodii astfel incat reprezentatia sa dureze exact N minute. De exemplu pentru $N$ = $3$, el are $3$ posibilitati de dispunere a melodiilor : $1, 2 ; 2, 1 ; 1, 1, 1$.

Gigel a fost invitat la aniversarea prietenei lui dragi, Alinuta, pe post de DJ. Principala lui problema este ca nu cunoaste decat $2$ melodii (prima dureaza $1$ minut, iar a doua $2$ minute), dar el a fost chemat pentru exact $N$ minute de reprezentatii.
 
Deoarece Gigel este student la FMI si nu la Conservator nu il deranjeaza acest lucru, in plus este curios sa stie pentru un N dat care este numarul de moduri de a dispune cele 2 melodii astfel incat reprezentatia sa dureze exact N minute. De exemplu pentru $N$ = 3, el are 3 posibilitati de dispunere a melodiilor : {1, 2} , {2, 1}, {1, 1, 1}.

Dupa ce a calculat pentru N <= 100 (cu backtracking) si-a dat seama ca acest numar este destul de mare, asa ca doreste sa afle doar restul impartirii acestui numar la R, numarul lui norocos. In plus el doreste raspunsul la aceasta intrebare pentru T valori diferite ale lui N.
h2. Date de intrare

Pe prima linie din fişierul de intrare $melodii.in$ se vor gasi valorile $T$ si $R$.
Pe urmatoarele T linii se va afla exact o singura valoarea ce va semnifica numarul $N$ de minute pentru testul respectiv.

Pe prima linie din fişierul de intrare $melodii.in$ se vor gasi valorile $T$ si $R$. Pe urmatoarele T linii se va afla exact o singura valoarea ce va semnifica numarul N de minute pentru testul respectiv.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ T, R ≤ 100 000$

* $1 ≤ N ≤ 10^18^$

* $1 ≤ N ≤ 10^18

* Pentru $50%$ din teste, $1 ≤ N ≤ 1 000 000$
h2. Exemplu
table(example). |_. melodii.in |_. melodii.out |

| 5 5
  1
  2
  3
  10
  666013
| 1
  2
  3
  10
  x

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

|
h3. Explicaţie