B. Merge it!

You are given an array aanna1,a2,…,ana1,a2,…,an

In one operation you can choose two elements of the array and replace them with the element equal to their sum (it does not matter where you insert the new element). For example, from the array [2,1,4][2,1,4][3,4][3,4][1,6][1,6][2,5][2,5]

Your task is to find the maximum possible number of elements divisible by 33

You have to answer tt

Input

The first line contains one integer tt1≤t≤10001≤t≤1000

The first line of each query contains one integer nn1≤n≤1001≤n≤100

The second line of each query contains nna1,a2,…,ana1,a2,…,an1≤ai≤1091≤ai≤109

Output

For each query print one integer in a single line — the maximum possible number of elements divisible by 3

代码：

1 #include
      
        2 #include
       
         3 using namespace std; 4 int main() { 5     int n,m; 6     cin>>n; 7     for(int i=0; i
        
         >m;12         for(int j=0; j
         
          >a[j];14             if(a[j]%3==0) {15                 cnt++;16             } else {17                 a[j]%=3;18                 b[cnt1++]=a[j];19             }20         }21         for(int i=0; i
          
           b1) {30             int h=a1-b1;31             if(h>=3) {32                 cnt+=h/3;33             }34             cnt+=b1;35         } else {36             int h=b1-a1;37             if(h>=3) {38                 cnt+=h/3;39             }40             cnt+=a1;41         }42         cout<
           
            <
           
          
         
        
       
      

思路分析：若本身可整除3就加1，将不可整除3的数模3，都转化成1和2，比较1和2的数量，1比2多那就配对2数量个3，然后看1比2多了几个，如果超过3，看有多少个3，再记数。

链接：