Counting Zero Bitwise AND Pairs

You are given several queries. For each query, you are given an integer ( n ) and an array of ( n ) integers. Your task is to count the number of valid pairs ( (i, j) ) such that ( 1 \leq i < j \leq n ) and the bitwise AND of ( a_i ) and ( a_j ) is zero, i.e. ( a_i , & , a_j = 0 ).

For each query, output the answer modulo ( 10^9+7 ).

inputFormat

The input is read from standard input (stdin). The first line contains a single integer ( t ), which denotes the number of queries. Each query consists of two lines:

• The first line contains a single integer \( n \) representing the length of the array.
• The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

For each query, output a single line containing the number of valid pairs ( (i, j) ) such that ( a_i , & , a_j = 0 ), taken modulo ( 10^9+7 ). The outputs for different queries should be printed on separate lines.## sample

1
4
1 2 4 8

6