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

Mitruţ are N beţe de lungimi egale şi nu prea ştie ce să facă cu ele. Voi îi daţi idea să formeze poligoane convexe din ele, iar el vă întreabă acum în câte feluri le poate grupa. Mitruţ vă sfătuieşte să vă uitaţi la exemplu pentru a înţelege mai bine ce vă cere.
 
h2.Cerinţă
 
Vi se pun T teste la dispoziţie. Pentru fiecare trebuie să afişaţi numărul de moduri în care se pot grupa beţele pentru a forma poligoane convexe regulate modulo un număr dat.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare poligoane.in conţine pe prima linie numărul T. Pe fiecare din următoarele T linii se află câte două numere Ni şi MODi.

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

h2. Date de ieşire

Fişierul de ieşire poligoane.out conţine T linii. Pe linia i se va afla numărul cerut pentru Ni modulo MODi.

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

h2. Restricţii

•	1 ≤ T ≤ 10
•	3 ≤ Ni ≤ 2 000
•	1 ≤ MODi ≤ 1 000 000

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

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

| 7
  3 7
  6 13
  4 17
  11 23
  12 19
  13 31
  799 666013
| 1
  2
  1
  6
  9
  10
  29846

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

|
h3. Explicaţie