该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

糖盒排队

题目描述

有 $n$ 个糖盒排成一排，第 $i$ 个糖盒里有 $a_i$ 颗糖。

你可以进行若干次操作。

每次操作可以选择两个相邻的糖盒，并从其中一个糖盒拿出一颗糖，放到另一个糖盒中。

也就是说，你可以选择一个位置 $i$，满足 $1 \le i < n$，然后执行以下两种操作之一：

• 从第 $i$ 个糖盒拿一颗糖放到第 $i+1$ 个糖盒；
• 从第 $i+1$ 个糖盒拿一颗糖放到第 $i$ 个糖盒。

要求拿糖的那个糖盒中至少有一颗糖。

请你求出，最少需要多少次操作，才能让所有糖盒中的糖果数量都变成偶数。

如果无论如何都做不到，输出 -1。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行输入一个整数 $n$，表示糖盒数量。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个糖盒中的糖果数量。

数据范围

对于所有测试数据，满足：

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示最少操作次数。

如果无法做到，输出 -1。

输入输出样例 #1

输入 #1

5
4
1 2 3 4
5
1 1 1 1 2
3
1 1 1
6
2 5 4 7 8 6
7
4 3 8 6 5 2 4

输出 #1

2
2
-1
2
3