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$ のすべての要素を等しくするために必要な最小の操作回数を求めるか、それが不可能であることを報告してください。

入力形式

この問題には複数のテストケースが含まれます。

1 行目にはテストケースの数を表す正の整数 $t$ ($1 \le t \le 10^5$) が与えられます。

各テストケースについて：

• 1 行目には正の整数 $n$ ($1 \le n \le 10^6$) が与えられます。
• 2 行目には $n$ 個の整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$) が与えられます。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証されます。

出力形式

各テストケースについて、1 行を出力してください：

• 不可能な場合は $-1$ を出力してください。
• 可能な場合は、数列 $a$ のすべての要素を等しくするために必要な最小の操作回数を表す整数を出力してください。

入出力例

入力例 1

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

出力例 1

1
2
-1

ノート

1 つ目のテストケースについて：

• 区間 $[1, 2]$ に対して操作を行う。数列は $2, 2$ となり、すべての要素が等しくなる。
• より少ない操作回数で達成する方法は存在しないことが証明できるため、答えは $1$ である。

2 つ目のテストケースについて：

• 区間 $[1, 4]$ に対して操作を行う。数列は $2, 4, 2, 4$ となる。
• 区間 $[1, 4]$ に対して操作を行う。数列は $3, 3, 3, 3$ となり、すべての要素が等しくなる。
• より少ない操作回数で達成する方法は存在しないことが証明できるため、答えは $2$ である。

3 つ目のテストケースについて：

• 何回操作を行ってもすべての要素を等しくすることは不可能であることが容易に証明できるため、答えは $-1$ である。