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$ 中的所有數字都相等。你需要幫助 Yuki 求出使序列 $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$。