Yuki는 길이가 $n$인 수열 $a$를 가지고 있습니다.

Yuki는 연산을 다음과 같이 정의합니다:

• 길이가 짝수인 구간 $[l, r]$을 선택합니다. $l \le i \le r$을 만족하는 모든 정수 $i$에 대하여:
  • $i - l$이 홀수이면 $a_i$의 값이 $1$ 감소합니다. 즉, $a_i \leftarrow a_i - 1$입니다.
  • $i - l$이 짝수이면 $a_i$의 값이 $1$ 증가합니다. 즉, $a_i \leftarrow a_i + 1$입니다.

이제 Yuki는 연산을 몇 번 수행하여 수열 $a$의 모든 수를 같게 만들고자 합니다. 수열 $a$의 모든 수를 같게 만들기 위해 필요한 최소 연산 횟수를 구하거나, 불가능하다면 이를 보고하세요.

입력 형식

이 문제는 여러 개의 테스트 케이스를 포함합니다.

첫 번째 줄에 테스트 케이스의 개수를 나타내는 양의 정수 $t$ ($1 \le t \le 10^5$)가 주어집니다.

각 테스트 케이스에 대하여:

• 첫 번째 줄에 양의 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.
• 두 번째 줄에 $n$개의 정수 $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$)이 주어집니다.

모든 테스트 케이스에서 $n$의 합은 $10^6$을 초과하지 않음이 보장됩니다.

출력 형식

각 테스트 케이스마다 한 줄을 출력합니다:

• 불가능하다면 $-1$을 출력합니다.
• 가능하다면 수열 $a$의 모든 수를 같게 만들기 위한 최소 연산 횟수를 나타내는 정수를 출력합니다.

예제

예제 입력 1

3
2
1 3
4
1 5 1 5
5
1 3 1 3 1

예제 출력 1

1
2
-1

노트

첫 번째 테스트 케이스에 대하여:

• 구간 $[1, 2]$에 연산을 수행합니다. 수열은 $2, 2$가 되어 모든 수가 같아집니다.
• 더 적은 연산 횟수로 가능한 방법이 없음을 증명할 수 있으므로 답은 $1$입니다.

두 번째 테스트 케이스에 대하여:

• 구간 $[1, 4]$에 연산을 수행합니다. 수열은 $2, 4, 2, 4$가 됩니다.
• 구간 $[1, 4]$에 연산을 수행합니다. 수열은 $3, 3, 3, 3$이 되어 모든 수가 같아집니다.
• 더 적은 연산 횟수로 가능한 방법이 없음을 증명할 수 있으므로 답은 $2$입니다.

세 번째 테스트 케이스에 대하여:

• 연산을 몇 번 수행하더라도 모든 수를 같게 만드는 것이 불가능함을 쉽게 증명할 수 있으므로 답은 $-1$입니다.