题目描述

小 Z 有一个长度为 $N$ 的数组 $A$。他最喜欢的数字是 $3$，所以他希望数组中的每个数都是 $3$ 的倍数。

小 Z 可以进行以下操作：

• 选择两个不同的索引 $i$ 和 $j$，将 $A_i$ 增加 $1$，同时将 $A_j$ 减少 $1$。

请问小 Z 至少需要多少次操作才能使数组中的所有数都变成 $3$ 的倍数？如果不可能，请输出 $-1$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例包含两行：

• 第一行包含一个整数 $N$，表示数组的长度。
• 第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N$，表示数组中的元素。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最小操作次数或 $-1$。

输入输出样例

3
3
1 2 3
4
6 3 9 12
2
4 3

1
0
-1

样例 $\tt \#1$ 说明

• 第一个测试用例：数组为 $[1, 2, 3]$。小 Z 可以选择索引 $1$ 和 $2$ 进行操作：将 $A_1$ 减少 $1$，将 $A_2$ 增加 $1$。操作后数组变为 $[0, 3, 3]$，所有元素都是 $3$ 的倍数。只需 $1$ 次操作。
• 第二个测试用例：数组为 $[6, 3, 9, 12]$，所有元素已经是 $3$ 的倍数，不需要操作。
• 第三个测试用例：数组为 $[4, 3]$，无法通过操作使所有元素变成 $3$ 的倍数，因此输出 $-1$。

数据范围

• 对于$20 \%$的数据，满足$A_i \% 3 \ne 1$。
• 对于另外$20 \%$的数据，满足$A_i \% 3 \ne 2$。
• 对于$100 \%$的数据，满足$1\leq T \leq 1000, 2 \le N \le 10^5, 1\le A_i \le 10^9$。