题目描述

给定一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成的数组 $a$。

每次操作，你可以选择数组中的两个元素，将它们替换为它们的和（新元素插入到数组中的位置无关紧要）。例如，从数组 $[2, 1, 4]$ 可以得到以下数组：$[3, 4]$、$[1, 6]$ 和 $[2, 5]$。

你的任务是，在任意次数（可以为零）地执行上述操作后，求数组中最多能有多少个元素是 $3$ 的倍数。

你需要回答 $t$ 个独立的询问。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示询问的数量。

每个询问的第一行包含一个整数 $n$（$1 \le n \le 100$）。

每个询问的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

输出格式

对于每个询问，输出一个整数，表示在任意次数地执行上述操作后，数组中最多能有多少个元素是 $3$ 的倍数。每个答案占一行。

说明/提示

在第一个样例中，你可以按如下操作序列得到 $3$ 个是 $3$ 的倍数的元素：$[3, 1, 2, 3, 1] \rightarrow [3, 3, 3, 1]$。

在第二个样例中，你可以通过如下操作得到 $3$ 个是 $3$ 的倍数的元素：$[1, 1, 1, 1, 1, 2, 2] \rightarrow [1, 1, 1, 1, 2, 3] \rightarrow [1, 1, 1, 3, 3] \rightarrow [2, 1, 3, 3] \rightarrow [3, 3, 3]$。

由 ChatGPT 4.1 翻译

样例

2
5
3 1 2 3 1
7
1 1 1 1 1 2 2

3
3