POLSKI SPOJ

Dany wielomian p(x)= a_nxⁿ + a_n-1x^n-1 + ... + a₀ o współczynnikach całkowitych. Należy znaleźć rozwiązanie równania p(x)=0 modulo 2¹⁵.

Wejście

W pierwszej linii znajduje się liczba naturalna T (1<=T<=150) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Pojedynczy zestaw testowy zbudowany jest następująco:
- w pierwszej linii znajduje się liczba n (1<=n<=40) stopień wielomianu
- w drugiej linii znajduje się opis wielomianu, tj. ciąg a₀ a₁ a₂ ... a_n (a_n != 0) liczb całkowitych z zakresu [-100,100].

Wyjście

Dla każdego zestawu testowego należy w osobnej linii wypisać dowolne rozwiązanie równania z przedziału [0,2¹⁵). Gwarantuje się, że dane testowe będą tak dobrane, aby rozwiązanie istniało.

Przykład

Input:
2
1
2 1
2
-40 3 1

Output:
32766
5