题目内容

小智和小灵在进行一个取数游戏。初始时有一堆非负整数。两人轮流行动，小智先手。每一轮中：

• 小智必须从堆中选取一个数并移除，记其值为 $x$；
• 小灵必须从剩余的数中寻找一个数 $y$，满足 $(x + y) \bmod 4 = 3$。若存在，则将其移除并获得 $1$ 分；若不存在，小灵无法行动，游戏立即结束。

小智希望小灵获得的总分尽可能少，小灵希望自己的总分尽可能多。双方均采取最优策略。请你计算最终小灵的得分。

在本题中，每组的数字个数 $n$ 不超过 2 * 10^5，所有测试组的 $n$ 之和也不超过 2 * 10^5。每个数字均为 $0$ 到 $10^9$ 之间的整数。

输入描述

第一行包含一个整数 $T$ $(1 \le T \le 10^4)$，表示数据组数。随后每组数据包含两行：第一行一个整数 $n$，表示该组数字的个数；第二行包含 $n$ 个整数，依次表示这些数字。所有测试数据的 $n$ 总和不超过 2 * 10^5。

输出描述

对于每组数据，输出一行，包含一个整数，表示在最优策略下小灵能得到的最高分数。

样例1

输入

1
1
5

输出

0

说明

堆中只有一个数字 5，其除以 4 的余数为 $1$。小智先手移除 5，此时堆已空，小灵需要寻找满足 $(x + y) \bmod 4 = 3$ 的 $y$，但无剩余数字，无法行动，游戏立即结束，小灵得 0 分。

样例2

输入

1
3
0 0 3

输出

1

说明

数字模 4 的余数分布为：余 0 有 2 个，余 3 有 1 个。配对组 $(0,3)$ 的数量不相等（$2 eq 1$）。小智可以采取最优策略：先选一个余 0 的数（$x$），小灵可以找到一个余 3 的数（$y$）满足 $(x+y) \bmod 4 = 3$，将其移除并得 1 分。此时剩余一个余 0 的数。小智再次选取该数，小灵需要余 3 的数但已没有，游戏结束。小灵最终得分为 1。

样例3

输入

1
4
0 3 1 2

输出

2

说明

数字模 4 的余数分布为：余 0、1、2、3 各 1 个。配对组 $(0,3)$ 数量相等（$1 = 1$），$(1,2)$ 数量也相等（$1 = 1$）。不存在数量不相等的非空配对组，小智无法提前终止游戏。在双方最优策略下，所有能够配对的数字都会配对成功，小灵每配对一次得 1 分，总得分为 $1 + 1 = 2$。