Ordered Pairs

3.6

13 votes
Medium-Hard
Problem

You have been given an integer array A of size N. You must report the number of ordered pairs (i,j) such that A[i] & A[j] is zero.
Here '&' denotes the BITWISE AND.
Note: pairs (i,j) and (j,i) are considered different.

Input
First line contains T-Number of Test cases. First line of each test contains N.
Next line contains N integers - the i'th integer A[i].
Output
Output the number of such pairs for each test case.

Constraints
T ≤ 10 N ≤ 100000 A[i] ≤ 1000000

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Here we have the pairs as (3,5) and (5,3).

Editor Image

?