3040: 牛老板搬山

彩虹岛作为一个美丽的小岛，有$n$座美丽的山，第$i$座山高度为$a_{i}$。彩虹岛岛主$dfd$是一个数字"$3$"的狂热爱好者，他希望尽可能多的山高度都是$3$ 的倍数。

于是$dfd$找到了牛老板来帮他搬山，牛老板每次可以将相邻的两座山合并成一座山。合并生成的山，高度为两座山高度之和。

$dfd$作为彩虹岛岛主，搞到了很多考研核心知识点。在牛老板搬完山后，每有一座高度为$3$的倍数的山，$dfd$就会给牛老板一个核心知识点，使牛老板在$18$考研中更有一丝把握。请问牛老板最多能获得多少核心知识点。
(注：假如一开始有四座山 $1\ 2\ 3\ 4$，牛老板合并中间两座山，变为$1\ 5\ 4$，那么认为$5$与$1$和$4$两座山相邻)

输入第一行为一个整数$T(T \leq 60)$，表示一共有$T$组测试数据。

对于每组测试数据：
第一行有一个整数$n(1 \leq n \leq 2*10^5)$，表示山的数量。

第二行有$n$个整数，其中第$i$个数$a_i(1 \leq a_i \leq 10^9)$，表示第$i$座山的高度。

对于每组测试数据输出一个整数$x$，表示牛老板能获得的核心知识点数目。

2
5
7 1 11 9 10
1
1

2
0