### 问题描述

小然有一个神秘的水果园，种植着各种丰富的水果。这个水果园有一个特别的规则，那就是园中的任何两棵树所结的果实总量，都必须能被 $3$ 整除。小然可以通过施肥来增加两棵树的果实总量。在一次施肥过程中，小然会选择园中的两棵树，然后对它们同时施肥，使得这两棵树的果实总量都增加到原来两棵树果实的总和。

例如，如果有两棵树原本分别结了 $4$ 个和 $8$ 个果实，小然施肥后，这两棵树的果实总量都会变为 $12$ 个。

现在，小然希望知道，要让整个果园的果实总量都满足“能被 3 整除”的规则，他最少需要进行多少次施肥操作。

输入格式

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

每组测试数据包含两行。第一行是一个整数 $N$，表示果园中树的数量。第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, ..., A_N$ ，分别代表果园中每棵树原本结的果实数量。

输出格式

对于每组测试数据，输出一个整数，表示小然最少需要进行的施肥操作数。

样例输入

2
4
4 8 20 16
4
4 3 6 9

样例输出

2
6

说明

在第一组测试中，小然可以通过以下步骤让整个果园的果实总量满足规则：

1. 选择第一棵和第二棵树施肥，果实总量变为 $4 + 8 = 12$。果园的果实分布变为 $[12, 12, 20, 16]$。
2. 选择第三棵和第四棵树施肥，果实总量变为 $20 + 16 = 36$。果园的果实分布变为 $[12, 12, 36, 36]$。

此时，果园中的每棵树的果实总量都能被 3 整除。小然总共进行了 2 次施肥操作。

在第二组测试中，小然需要进行 6 次施肥操作，最终果园的果实分布为 $[42, 42, 42, 42]$。

评测数据范围

$1 \leq T \leq 1000$，$4 \leq N \leq 10^5$，$1 \leq A_i \leq 10^5$。

所有测试数据中 $N$ 的总和不超过 $2 \times 10^5$。