$2027$ 届 $2$ 班何其远在出题人面前关上带密码的门浪费出题人宝贵的 $10$ 秒，在此谴责。

题目背景

“什么垃圾习惯，怎么考上__班，正是令人费解”

yuno 所在班级的化学老师如是说道。

题目描述

yuno 的同学们习惯太差了，老师有可能将这个班拆散。可 yuno 不想让她的 yuki 掉出一班，她需要提升班中同学的习惯。

yuno 班上共有 $n$ 位同学，同学的习惯是一个序列 $h_i$，当序列中的任意相邻三个数之和是 $3$ 的倍数，则称同学们的习惯是好的。

yuno 每次可以执行以下操作：

• 提升其中一位同学的习惯，即选择 $1\le i \le n$，令 $h_i \gets h_i + 1$。

然而 yuno 只想和她的 yuki 交流，并不想和别的同学打交道，应此她想知道她最小需要的操作次数。

输入格式

第一行一个整数 $T$ 代表数据组数，对于每一组数据：

第一行一个整数 $n$，表示 yuno 有多少同学。

第二行有 $n$ 个整数，对于第 $i$ 个整数 $h_i$，表示第 $i$ 位同学的习惯。

输出格式

对于每组数据，一行一个整数表示最小操作次数。

样例 #1

样例输入 #1

1
3
1 3 5

样例输出 #1

0

样例 #2

样例输入 #2

1
10
2 3 10 25 12 7 10 12 1 46

样例输出 #2

3

提示

对于 $100\%$ 的数据，保证 $1 \le T \le 10,3 \le n \le 10^5,~1\le h_i \le 10^9$。