Chef Tobby is trying to run a code given to him by Bhuvan for an experiment they want to include in the manuscript to be submitted to a conference. The deadline to submit the manuscript is within a couple of hours and Chef Tobby needs to finish the experiments before then.
The code given by Bhuvan is the following which runs given an array of N integers and another integer K :
void recurse ( array a, int n )
{
	// n = size of array
	define array b currently empty
	consider all 2^n subsets of a[]
	{
		x = bitwise OR of elements in the subsets
		add x into "b" if it is not present yet
	}
	if (sizeof( b ) == 1 << k)
	{
		printf(“Won”);
		return;
	}
	recurse ( b, sizeof( b ) );
}

Chef Tobby tried to run an experiment with only one integer in the array with value 2 and K = 3. To his horror, he found out that the algorithm is resulting in an infinite loop. He is livid with the possibility that the algorithm can lead to infinite loops for certain cases. On closer inspection he determines that it might be possible to insert additional elements in the initial array to subvert the problem. Since time is very less, Chef Tobby would like to insert the minimum number of elements.
Chef Tobby has to finish writing the paper, so he asks his graduate student Leamas to fix it. Leamas has no idea how to fix the problem so he asks you for help.

-----Input section-----
The first line contains T, the number of test cases.
Each test case consists of 2 lines. The first line contains 2 integers N and K, denoting the number of elements in the array and parameter mentioned in problem statement.
Next line contains N space separated integers, denoting the elements of the array.

-----Output section-----
Output the minimum number of elements that need to be inserted so that inifinite loop can be avoided.

-----Input constraints-----
1 ≤ T ≤ 10
1 ≤ Sum of N over all test cases ≤ 105
1 ≤ K ≤ 20
0 ≤ A[i] ≤ 2K-1, where A[i] denotes the ith element of the array.

-----Sample Input - 1-----
1
2 2
3 1

-----Sample Output - 1-----
1

-----Explanation - 1-----
You can win the game by inserting the element 2 into the array.

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

-----Sample Output - 2-----
0

-----Explanation - 2-----
The initial array will result will terminate in the first step of algorithm only. Thus there is no need to insert any new element.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from bisect import *
for x in range(eval(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	t = 1
	result = 0
	y = 0
	while y < n:
		if arr[y] < t:
			y += 1
		elif arr[y] == t:
			t = t * 2
			y += 1
		else:
			result += 1
			t = t * 2
	while t < 2 ** k:
		result += 1
		t = t * 2
	print(result)


t = eval(input())
x = [2 ** i for i in range(0, 20)]
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = set(map(int, input().split()))
	count = 0
	for i in x:
		if i in arr:
			count += 1
	if k - count <= 0:
		print(0)
	else:
		print(k - count)


def pow2(n):
	return n and (not n & n - 1)
for T in range(eval(input())):
	(n, k) = list(map(int, input().strip().split()))
	data = list(map(int, input().strip().split()))
	ans = set()
	for i in data:
		if pow2(i):
			ans.add(i)
	print(k - len(set(ans)))


t = eval(input())
for i in range(0, t):
	ar = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	count = 0
	for j in range(0, ar[1]):
		z = 1 << j
		if z not in arr:
			count += 1
	print(count)


t = eval(input())
for tt in range(t):
	nk = input().split()
	n = int(nk[0])
	k = int(nk[1])
	lis = input().split()
	for i in range(n):
		lis[i] = int(lis[i])
	tmp = []
	for i in range(k):
		tmp.append(1 << i)
	count = 0
	for i in tmp:
		if i not in lis:
			count += 1
	print(count)


for _ in range(eval(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	elementsNeeded = [pow(2, i) for i in range(k)]
	ans = 0
	for i in elementsNeeded:
		if not i in a:
			ans += 1
	print(ans)


for _ in range(eval(input())):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	l = [int(x) for x in input().split()]
	s1 = set(l)
	c = k
	for i in range(k):
		if 1 << i in s1:
			c -= 1
	print(max(c, 0))


pow2 = [1 << i for i in range(21)]
for t in range(eval(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	cnt = 0
	for i in range(k):
		if pow2[i] not in l:
			cnt += 1
	print(cnt)