Problema: giovanacci / 
Autor: Cerința
Șirul Fibonacci este definit după regula:- \(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.
