QQQQQQQ的数组

QQQQQQQ得到了一个由n个整数a1，a2，…，an组成的数组a。

在一个操作中，Shmily可以选择数组中的任意个元素，并将它们替换为等于其和的元素（在何处插入新元素并不重要）。例如，从数组[2,1,4]可以获得以下几种数组：[3,4]、[1,6]、[2,5]和[7]。

QQQQQQQ的任务是在执行任意（可能为零）次操作后，找到数组中可被4整除的元素的最多的数目。QQQQQQQ觉得太easy了，就交给你们了

第一行包含一个整数t（1≤t≤1000）表示有t组。

每个查询的第一行包含一个整数n（1≤n≤100）。

每个查询的第二行包含n个整数a1，a2，…，an（0≤ai≤10⁹）。

对于每个查询，在一行中输出一个整数在执行任意次操作后，数组中可被4整除的元素的最大可能的数。

3
3
2 1 4
4
1 2 3 4
6
0 0 0 0 0 0

1
2
6