You are given an array A of N numbers, output the count of pairs in the array whose sum is divisible by 4.
The first line of the input contains a single integer T denoting the number of test cases.
The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers
A[0] A[1] ... A[N−1]
representing the array numbers.
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Main {
public static void main (String[] args) throws java.lang.Exception {
//Scanner scan = new Scanner(System.in);
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
//int t= scan.nextInt();
while (t-- > 0) {
int n = Integer.parseInt(br.readLine());
long ans=0;
int[] arr= new int[n];
String line = br.readLine();
String[] strs = line.trim().split("\\s+");
for (int i = 0; i < n; i++) {
arr[i]=Integer.parseInt(strs[i]);
}
int[] count = new int[4];
for (int i = 0; i < n; i++) {
count[arr[i] % 4]++;
}
for (int i = 1; i <= 1; i++) {
ans += count[i] * count[4-i];
}
ans += (count[2] * (count[2]-1)) / 2;
//System.out.println(ans);
ans += (count[0] * (count[0]-1)) / 2;
System.out.println(ans);
}
}
}