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.