题目背景

给定两种操作：

• 从数组中选择一个元素，将该元素删除，使得数组长度减少 $1$ 。

• 从数组中选择一个元素，将该元素增加 $1$ 。

题目描述

现在给定一个有 $n$ 个元素的数组，进行以上操作任意次，如果数组为空将不能进行操作。

现在请问最少需要多少次可以让数组元素之和能够被 $3$​ 整除。

PS：空数组元素之和为 $0$ 。

输入格式

输入多行。

第一行输入一个 $t$ ，代表有 $t$​ 组测试数据。

对于每一组测试数据，第一行输入一个正整数 $n$ ，代表元素个数；第二行输入 $n$ 个正整数 $a_i$ 。

输出格式

输出多行。

对于每一组测试数据，输出最少的操作次数。

样例 #1

样例输入 #1

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

样例输出 #1

1
0
0
1
1
2
1
1

提示

样例解释】：

• 对于第一组测试样例：初始数组为 2 2 5 4 ，最好的方法就是将第 $4$ 个元素删除，这样数组就变成了 2 2 5 ，数组中元素之和为 $2 + 2 + 5 = 9$ ，能够被 $3$ 整除。

数据范围】：

对于 $100\%$ 的数据，保证 $1 \leq t \leq 10^3, 1 \leq n \leq 10^{5}, 1 \leq a_i \leq 10^4$​​ 。