Problem: After you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3».

The game has (m + 1) players and n types of soldiers in total. Players «Call of Soldiers 3» are numbered form 1 to (m + 1). Types of soldiers are numbered from 0 to n - 1. Each player has an army. Army of the i-th player can be described by non-negative integer xi. Consider binary representation of xi: if the j-th bit of number xi equal to one, then the army of the i-th player has soldiers of the j-th type. 

Fedor is the (m + 1)-th player of the game. He assume that two players can become friends if their armies differ in at most k types of soldiers (in other words, binary representations of the corresponding numbers differ in at most k bits). Help Fedor and count how many players can become his friends.

Input

The first line contains three integers n, m, k (1 ≤ k ≤ n ≤ 20; 1 ≤ m ≤ 1000).

The i-th of the next (m + 1) lines contains a single integer xi (1 ≤ xi ≤ 2n - 1), that describes the i-th player's army. We remind you that Fedor is the (m + 1)-th player.

Output

Print a single integer — the number of Fedor's potential friends.

Examples

Input

7 3 1
8
5
111
17


Output

0


Input

3 3 3
1
2
3
4


Output

3

Solution (in PYTHON3):

Solution:
def binary(x):
	sum=0
	i=0
	list=[]
	while x>0:
		a=x%2
		x=x//2
		list.insert(len(list),a)
	for x in list:
		sum+=x*(10**i)
		i+=1
	return sum
def check(x,y,k):
	c=0
	while x>0 or y>0:
		a=x%10
		b=y%10
		x=x//10
		y=y//10
		#print(a,' ',b)
		if a==b:
			pass
		else:
			c+=1
	#print('\n')
	if c<=k:
	#	print(c,' ',k)
		return 1
	else :
		return 0


n,m,j=input().split()
m=int(m)
n=int(n)
j=int(j)
arr=[]
i=0
k=0
while i <m+1 :
	c=int(input())
	arr.insert(0,binary(c))
	i+=1
#print(arr)
for x in arr:
	if check(x,arr[0],j):
		k+=1
print(k-1)