Priya loves bitwise AND, but she hates programming. Help her solve this problem.

Given an array $A$ of size $N$, let $B_{ij}$  denote the [bitwise AND] of $A[i]$ and $A[j]$. You have to find the number of pairs $(i, j)$, such that $i < j$ and $B_{ij} = A[i]$.

------ Input: ------
The first line of the input contains a single integer $T$ denoting the number of test cases. 
The first line of each test case consists of a single integer $N$, denoting the Size of Array $A$. 
The second line of each test case contains $N$ space-separated integers $A_{1}, A_{2}, A_{3} ... A_{N}$.

------ Output: ------
For each test case, output a single line, count of such pairs.

------ Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$1 ≤ A[i] ≤ 100$

----- Sample Input 1 ------ 
2
5
1 1 1 1 1
1
10
----- Sample Output 1 ------ 
10
0
----- explanation 1 ------ 
Example case 1: Number of valid pairs are -$(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)$ and $(4,5)$. Therefore, total valid pairs $= 10$.

Example case 2: Since $N=1$, therefore there are no valid pairs.

Difficulty: EASY
Tags: Bit manipulation

Mathematics

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] & a[j] == a[i]:
				c += 1
	print(c)


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = list(map(int, input().split()))
	aim = 0
	for stress in range(wife):
		for death in range(stress + 1, wife):
			if life[stress] == life[stress] & life[death]:
				aim += 1
	print(aim)


for i in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(N):
		for j in range(i + 1, N):
			if l[i] == l[i] & l[j]:
				c += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	integers = list(map(int, input().split()))
	count = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if integers[i] & integers[j] == integers[i]:
				count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	c = 0
	for i in range(len(s) - 1):
		for j in range(i + 1, len(s)):
			if s[i] == s[i] & s[j]:
				c += 1
	else:
		print(c)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pairs = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if a[i] & a[j] == a[i]:
				pairs = pairs + 1
	print(pairs)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	s = 0
	for j in range(N - 1):
		for k in range(j + 1, N):
			c = A[j] & A[k]
			if c == A[j]:
				s += 1
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	pairs = 0
	for i in range(n):
		for j in range(i + 1, n):
			if lst[i] & lst[j] == lst[i]:
				pairs += 1
	print(pairs)


t = int(input())
for tc in range(t):
	x = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(x):
		for k in range(j + 1, x):
			if a[j] & a[k] == a[j]:
				count += 1
	print(count)


for case in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			if l[i] & l[j] == l[i]:
				c += 1
	print(c)


def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			count += A[i] & A[j] == A[i]
	return count
t = int(input())
while t:
	print(solve())
	t -= 1


def countPairs(arr, n):
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] & arr[j] == arr[i]:
				count += 1
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(countPairs(arr, n))


for _ in range(int(input())):
	length = int(input())
	count = 0
	inputstr = list(map(int, input().split()))
	for i in range(length - 1):
		for j in range(i + 1, length):
			if inputstr[i] & inputstr[j] == inputstr[i]:
				count += 1
	print(count)


t = int(input())
for v in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for k in range(n):
		for j in range(k + 1, n):
			if a[k] & a[j] == a[k]:
				c += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	count = 0
	for i in range(len(L)):
		for j in range(i + 1, len(L)):
			if L[i] & L[j] == L[i]:
				count += 1
	print(count)


for t in range(int(input())):
	n = int(input())
	a = [int(A) for A in input().split()]
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] & a[j] == a[i]:
				count += 1
	print(count)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	pairs = 0
	for i in range(len(A)):
		for j in range(i + 1, len(A)):
			if A[i] & A[j] == A[i]:
				pairs += 1
	print(pairs)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = 0
	for j in range(n):
		for k in range(j + 1, n):
			if a[j] & a[k] == a[j]:
				d += 1
	print(d)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1:
		print(0)
	else:
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				if a[i] == a[i] & a[j]:
					ans += 1
		print(ans)


t = int(input())
for T in range(t):
	n = int(input())
	l = []
	counts = 0
	l = list(map(int, input().split()))
	for i in range(n):
		for j in range(i + 1, n):
			if l[i] & l[j] == l[i]:
				counts = counts + 1
	print(counts)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l) = (IN(), I())
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			if l[i] & l[j] == l[i]:
				c += 1
	print(c)


for k in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	c = 0
	for i in range(len(A)):
		a = A[i]
		for j in range(i + 1, len(A)):
			b = A[i] & A[j]
			if a == b:
				c = c + 1
			else:
				c = c
	print(c)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	count = 0
	for i in range(N):
		for j in range(i + 1, N):
			count += A[i] & A[j] == A[i]
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))[:n]
	sorted(l)
	cnt = 0
	if n == 1:
		print(0)
	else:
		for i in range(n - 1):
			for j in range(i + 1, n):
				if l[i] & l[j] == l[i]:
					cnt += 1
		print(cnt)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	for j in range(n):
		for k in range(j + 1, n):
			if arr[k] & arr[j] == arr[j]:
				cnt = cnt + 1
	print(cnt)


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = a[:n]
	k = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if a[i] == a[i] & a[j]:
				k += 1
	print(k)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] == a[i] & a[j]:
				k = k + 1
	print(k)


def solution(n, a):
	if n == 1:
		return 0
	count = 0
	temp = []
	for i in range(1, n):
		for j in range(i, n):
			if a[i - 1] & a[j] == a[i - 1]:
				count += 1
	return count
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	print(solution(n, a))


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	c = 0
	for x in range(a):
		for y in range(x + 1, a):
			if l[x] & l[y] == l[x]:
				c += 1
	print(c)


test = int(input())
for i in range(test):
	arraysize = int(input())
	array_value = list(map(int, input().split()))
	count = 0
	for j in range(arraysize):
		for k in range(j + 1, arraysize):
			b = array_value[j] & array_value[k]
			if arraysize == 1:
				count = 0
			elif b == array_value[j]:
				count = count + 1
	print(count)


from itertools import combinations
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	if len(a) == 1:
		print(0)
	else:
		for c in combinations(a, 2):
			if c[0] == c[0] & c[1]:
				cnt += 1
		print(cnt)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	x = 0
	for i in range(N):
		for j in range(i + 1, N):
			if A[i] & A[j] == A[i]:
				x += 1
	print(x)


for tc in range(int(input())):
	n = int(input())
	x = [int(x) for x in input().split()]
	cnt = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if x[i] & x[j] == x[i]:
				cnt += 1
	print(cnt)


T = int(input())
for i in range(T):
	N = int(input())
	A = input().split()
	count = 0
	if N < 2:
		print(0)
	else:
		for x in range(0, N - 1):
			for y in range(x + 1, N):
				if int(A[x]) & int(A[y]) == int(A[x]):
					count += 1
		print(count)