POLSKI SPOJ

Jaś ma nie za ciekawą sytuacje z języka polskiego , wie że Pani liczy średnią z ocen. Spytał się Pani czy mogła by policzyć średnią kwadratową , Pani niepewnie ale się zgodziła , jednak zastrzegła fakt że to co wyjdzie z średnie zaokrągla w dół (jeśli wyjdzie 3.99 to wystawi 3 jeśli zaś wyjdzie 4 to wystawi 4). Jaś obliczył sobie średnią kwadratową i nadal nie jest zadowolony z tego wyniku. Więc spytał się czy może być średnia do potęgi k-tej a nie kwadratowej . Pani niepewnie się zgodziła , myśli że ma to mały wpływ na końcowy wynik. Jaś jednak chce wybrać jak najmniejsze k by Pani się nie poznała jakie znaczenie ma liczba k (k powinno być najmniejszą naturalną liczbą).

Średnia=^k√((a₁^k+a₂^k+a₃^k+...+a_n^k)/n)

Input

W pierwszej linijce jest liczba t-liczba zestawów.                                0<t<100001

W każdym zestawie na początku jest liczba n-liczba ocen                  0<n<1001

Następnie jest n ocen                                                                     1<=a_i<=6

Output

Należy dla każdego zestawu wypisać najmniejszą naturalną liczbę k dla której Jasiowi wyjdzie 4.

Zaś jeśli nie jest to możliwe dla k naturalnego należy wypisać -1

Example

Input:
4
5
1 2 3 1 3
4
1 2 3 5
5
1 1 5 1 1
2
4 2

Output:
-1
6
8
-1