Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef has array A consisting of N integers. He calls a sub-array of the array good if the bitwise OR of all the elements in it is greater or equal than number K. Please help him to find out how many sub-arrays of array A are good!

------ Input ------ 

The first line of input contains T - number of test cases. T test cases follow.
For each test case, first line contains an integer N - number of elements in array, and integer K.
Second line contains N space separated non-negative integers denoting array A. 

------ Output ------ 

For each test case, output an integer corresponding to the number of good sub-arrays of A in separate line. 

------ Constraints ------ 

1 ≤ T, N, ≤ 100,000
0 ≤ A_{i}, K ≤ 10^{9}
1 ≤ Sum over all values of N in the input in a single test file 
≤ 100,000

----- Sample Input 1 ------ 
2
3 3
1 2 3
3 6
3 4 5
----- Sample Output 1 ------ 
4
2

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Sorting

Amortized analysis

Range queries

Complete search

Segment trees revisited

Mathematics

Data structures


Solutions:
from collections import defaultdict

def get_active_bits(n):
	result = []
	i = 0
	while n:
		if n & 1:
			result.append(i)
		i += 1
		n >>= 1
	return result

def get_val(d):
	result = 0
	for (key, val) in d.items():
		if val:
			result += 2 ** key
	return result
t = int(input())
while t:
	n = input().split()
	k = int(n[1])
	n = int(n[0])
	a = [int(_) for _ in input().split()]
	(i, j, ans) = (0, 0, 0)
	dd = defaultdict(int)
	while j < n:
		while j < n and get_val(dd) < k:
			new_bits = get_active_bits(a[j])
			for each in new_bits:
				dd[each] += 1
			j += 1
		while i <= j and get_val(dd) >= k:
			ans += n - j + 1
			new_bits = get_active_bits(a[i])
			for each in new_bits:
				dd[each] -= 1
			i += 1
	print(ans)
	t -= 1