Yuki ha una sequenza $a$ di lunghezza $n$.

Yuki definisce un'operazione come segue:

• Scegli un intervallo $[l, r]$ di lunghezza pari. Per ogni intero $i$ tale che $l \le i \le r$:
  • Se $i - l$ è dispari, il valore di $a_i$ diminuisce di $1$, cioè $a_i \leftarrow a_i - 1$.
  • Se $i - l$ è pari, il valore di $a_i$ aumenta di $1$, cioè $a_i \leftarrow a_i + 1$.

Ora, Yuki vuole eseguire un certo numero di operazioni in modo che tutti i numeri nella sequenza $a$ siano uguali. Devi aiutare Yuki a trovare il numero minimo di operazioni necessarie per rendere uguali tutti i numeri nella sequenza $a$, oppure segnalare se è impossibile.

Input

Questo problema contiene più casi di test.

La prima riga contiene un intero positivo $t$ ($1 \le t \le 10^5$), che rappresenta il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene un intero positivo $n$ ($1 \le n \le 10^6$).
• La seconda riga contiene $n$ interi $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

È garantito che la somma di $n$ su tutti i casi di test non supera $10^6$.

Output

Per ciascun caso di test, stampa una riga:

• Se è impossibile, stampa $-1$.
• Se è possibile, stampa un intero che rappresenta il numero minimo di operazioni per rendere uguali tutti i numeri nella sequenza $a$.

Esempi

Input 1

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

Output 1

1
2
-1

Note

Per il primo caso di test:

• Esegui l'operazione sull'intervallo $[1, 2]$. La sequenza diventa $2, 2$, in cui tutti i numeri sono uguali.
• Si può dimostrare che non esiste alcuna soluzione con meno operazioni, quindi la risposta è $1$.

Per il secondo caso di test:

• Esegui l'operazione sull'intervallo $[1, 4]$. La sequenza diventa $2, 4, 2, 4$.
• Esegui l'operazione sull'intervallo $[1, 4]$. La sequenza diventa $3, 3, 3, 3$, in cui tutti i numeri sono uguali.
• Si può dimostrare che non esiste alcuna soluzione con meno operazioni, quindi la risposta è $2$.

Per il terzo caso di test:

• È facile dimostrare che è impossibile rendere uguali tutti i numeri indipendentemente dal numero di operazioni, quindi la risposta è $-1$.