비트 개수 수열

음이 아닌 정수 $x$에 대해, $p(x)$를 $x$의 이진 표현에서 1의 개수라고 하자. 예를 들어 $26 = (11010)_2$이므로 $p(26) = 3$이다.

정수 수열 $(a_1, a_2, \dots, a_n)$이 주어진다. $(p(x), p(x+1), \dots, p(x+n-1))$이 $(a_1, a_2, \dots, a_n)$과 같아지는 음이 아닌 정수 $x$가 존재하는지 판별하라. 존재한다면 그 조건을 만족하는 가장 작은 $x$를 구하라.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 1000$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 정수 $n$ ($1 \le n \le 500000$)이 주어진다. 둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 60$)이 주어진다.

모든 테스트 케이스에 걸친 $n$의 합은 500000을 넘지 않는다.

각 테스트 케이스에 대해, 조건을 만족하는 가장 작은 음이 아닌 정수 $x$를 출력한다. 그러한 $x$가 없다면 -1을 출력한다.