题目内容

给定一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$，米小游和你在这个数组上进行一场博弈，米小游先手；在每一轮中：

• 米小游操作：若数组非空，米小游必须从数组中取出一个元素，记为 $x$；
• 你操作：你检查剩余数组中是否存在元素 $y$ 满足 $(x + y) \bmod 4 = 3$。若存在，则必须从中取出一个并记一分；若不存在，则无法操作。
• 游戏交替进行，直到某一方无法执行其操作为止。

米小游希望使你的得分尽可能少，你希望自己的得分尽可能多。你们双方均采取最优策略，求最终你的得分。

输入描述

每个测试文件包含多组测试数据。 第一行输入一个整数 $T\ (1 \le T \le 10^4)$，表示测试数据组数； 每组测试数据包含两行：

• 第一行输入一个整数 $n\ (1 \le n \le 2 \times 10^5)$，表示数组长度；
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (0 \le a_i \le 10^9)$，表示数组元素。

除此之外，保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一个整数，表示你在对抗最优策略下的最终得分。

样例1

输入

2
3
1 2 3
4
0 0 3 3

输出

0
2

说明

• 对于第一组测试数据，米小游选择 $3$，你找不到满足条件的 $y$，直接结束游戏，得分为 $0$。