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$。