This was question i faced during hp thinkathon (contest has ended).What should be the approach to reduce time complexity less than bruteforce(O(n*n))

You have been given an integer array A on 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.
(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 ith integer A[i].
Output
Output the number of such pairs for each test case.

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

Sample Input()
1
5
41 47 34 40 29 
Sample Output(Plaintext Link)
 2
Explanation
These are the required pairs 3 5 5 3