Yuki possède une suite $a$ de longueur $n$.

Yuki définit une opération comme suit :

• Choisir un intervalle $[l, r]$ de longueur paire. Pour chaque entier $i$ tel que $l \le i \le r$ :
  • Si $i - l$ est impair, la valeur de $a_i$ diminue de $1$, c'est-à-dire $a_i \leftarrow a_i - 1$.
  • Si $i - l$ est pair, la valeur de $a_i$ augmente de $1$, c'est-à-dire $a_i \leftarrow a_i + 1$.

Maintenant, Yuki souhaite effectuer un certain nombre d'opérations de sorte que tous les nombres de la suite $a$ soient égaux. Vous devez aider Yuki à trouver le nombre minimum d'opérations nécessaires pour rendre tous les nombres de la suite $a$ égaux, ou signaler si cela est impossible.

Entrée

Ce problème contient plusieurs cas de test.

La première ligne contient un entier positif $t$ ($1 \le t \le 10^5$), représentant le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient un entier positif $n$ ($1 \le n \le 10^6$).
• La deuxième ligne contient $n$ entiers $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez une ligne :

• S'il est impossible d'y parvenir, affichez $-1$.
• S'il est possible d'y parvenir, affichez un entier représentant le nombre minimum d'opérations pour rendre tous les nombres de la suite $a$ égaux.

Exemples

Entrée 1

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

Sortie 1

1
2
-1

Note

Pour le premier cas de test :

• Effectuez l'opération sur l'intervalle $[1, 2]$. La suite devient $2, 2$, où tous les nombres sont égaux.
• On peut prouver qu'il n'existe aucune solution utilisant moins d'opérations, donc la réponse est $1$.

Pour le deuxième cas de test :

• Effectuez l'opération sur l'intervalle $[1, 4]$. La suite devient $2, 4, 2, 4$.
• Effectuez l'opération sur l'intervalle $[1, 4]$. La suite devient $3, 3, 3, 3$, où tous les nombres sont égaux.
• On peut prouver qu'il n'existe aucune solution utilisant moins d'opérations, donc la réponse est $2$.

Pour le troisième cas de test :

• Il est facile de prouver qu'il est impossible de rendre tous les nombres égaux quel que soit le nombre d'opérations, donc la réponse est $-1$.