Little MS는 칼 $n$개를 모아 놓았으며, $i$번째 칼의 절단 능력은 $a_i$입니다. 거대한 케이크를 조각으로 잘라야 하지만, 이 매우 중요한 일을 위해 자신의 칼 중 어떤 것을 골라야 할지 결정하지 못하고 있습니다.

얼마 후 Little MS는 칼의 비어 있지 않은 부분집합을 균등한 확률로 무작위로 고르기로 했습니다. 즉, 각 부분집합이 선택될 확률은 $\frac{1}{2^n-1}$입니다. 그런 다음 선택한 칼을 모두 임의의 순서로 사용합니다. 절단 능력이 $x$인 칼은 현재의 각 조각을 더 작은 조각 $x$개로 자릅니다. 결국 Little MS는 $a_{i_1}\cdot\ldots\cdot a_{i_k}$개의 조각을 얻게 되며, 여기서 $i_1,\ldots,i_k$는 선택한 칼의 번호입니다.

Little MS가 정확히 $s$개의 케이크 조각을 얻게 될 확률이 $50\%$보다 엄격히 큰 수 $s$가 존재하는지 판단하도록 도와주세요.

입력

첫 번째 줄에는 테스트 케이스의 수인 정수 $t$ ($1\le t\le 10^4$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 칼의 수인 정수 $n$ ($2\le n\le 2\cdot 10^5$)이 주어집니다.

각 테스트 케이스의 두 번째 줄에는 정수 $n$개 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$)이 주어집니다. 여기서 $a_i$는 $i$번째 칼의 절단 능력입니다.

모든 테스트 케이스에 대한 $n$의 합은 $2\cdot 10^5$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해 적절한 수 $s$가 없다면 $-1$을 출력하세요.

그렇지 않다면 Little MS가 정확히 $s$개의 케이크 조각을 얻게 될 확률이 $50\%$보다 엄격히 큰 수 $s$를 출력하세요.

예제

입력 1

4
2
2 3
2
100 100
3
2 2 2
4
1 1 1 1

출력 1

-1
100
-1
1

참고

첫 번째 테스트 케이스에서 칼의 비어 있지 않은 모든 부분집합에 대해 가능한 곱은 $2$, $3$, $6$입니다. 각각 한 번씩 나타나므로 어느 것도 $50\%$보다 엄격히 큰 확률로 얻을 수 없습니다. 따라서 답은 $-1$입니다.

두 번째 테스트 케이스에서 칼의 비어 있지 않은 모든 부분집합에 대해 가능한 곱은 $100$, $100$, $10000$입니다. 곱 $100$은 3가지 경우 중 2가지에서 나타나므로 그 확률은 $50\%$보다 엄격히 큽니다. 따라서 답은 $100$입니다.

세 번째 테스트 케이스에서 칼의 비어 있지 않은 모든 부분집합에 대해 가능한 곱은 $2$, $2$, $2$, $4$, $4$, $4$, $8$입니다. 절반보다 많이 나타나는 곱이 없으므로 답은 $-1$입니다.