B. 龟速数学题：三的快速任务
每个测试点时间限制：2 秒
内存限制：256 兆字节

题目描述

你有一个数组 $a_1, a_2, \dots, a_n$。

在每一步操作中，你可以执行以下两种操作之一：

1. 从数组中选择一个元素并将其删除。结果数组的长度减少 $1$。
2. 从数组中选择一个元素并将其值增加 $1$。

你可以执行任意多次操作。如果当前数组变为空，则不能再进行任何操作。

你的任务是：找出最少需要多少次操作，使得数组所有元素的和能被 $3$ 整除。
有可能需要 $0$ 次操作。

注意：空数组（长度为 $0$ 的数组）的和等于 $0$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的输入格式如下：

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^4$）。

所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数：最少需要的操作次数。

示例

输入

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
0
0
1
1
2
1
1

样例说明

• 第一个测试用例：初始数组 $[2,2,5,4]$。
  最优操作之一：删除第 $4$ 个元素，得到 $[2,2,5]$，和为 $9$，能被 $3$ 整除。
  操作次数 = $1$。

• 第二个测试用例：初始数组 $[1,3,2]$，和为 $6$，能被 $3$ 整除，不需要操作。
  操作次数 = $0$。

• 第四个测试用例：初始数组 $[1]$，和为 $1$，不能被 $3$ 整除。
  删除唯一元素，得到空数组，和为 $0$，能被 $3$ 整除。
  操作次数 = $1$。