Cerința

• $F_1 = 1$
• $F_2 = 1$
• $F_n = F_{n – 1} + F_{n – 2}$

Comisia mafioților îl supune pe Giovanni la T teste. Pentru fiecare test se dau n și apoi n numere naturale ${pos}_1, {pos}_2, …, {pos}_n$ reprezentând poziții în șirul Fibonacci. Se cere să se găsească cel mai mare număr g care divide $F_{{pos}_1}, F_{{pos}_2}, …, F_{{pos}_n}$. Comisia a înțeles că Giovanni nu poate reține numere mari, așa că îi cere să afișeze restul împărțirii lui g la numărul p. Fiind depășit de cerință, mafiotul are opțiunea să sune publicul și vă contactează pe voi. Ajutați-l pe Giovanni să-și mențină demnitatea și el vă va răsplăti cu un punctaj pe măsură.

Date de intrare

Fișierul de intrare giovanacci.in conține pe prima linie numerele T și p, iar pe următoarele T linii n, urmat de n numere naturale.

Date de ieșire

Fișierul de ieșire giovanacci.out va conține cele T răspunsuri, câte unul pe linie.

Restricții și precizări

• $1 ≤ T ≤ 10^3$
• $2 ≤ p ≤ 10^5$
• $1 ≤ n ≤ 10^3$
• $1 ≤ pos_i ≤ 10^{17}$

Exemplu:

giovanacci.in

2 2
3 6 9 12
2 5 10

giovanacci.out

0
1

Explicație

Sunt 2 teste. Pentru primul test, 2 este cel mai mare număr care divide 8, 34, 144. Pentru al doilea test, 5 este cel mai mare număr care divide 5 și 55. Răspunsurile s-au afișat modulo 2.