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:
#
import sys

#
# inf = float("inf")
# # sys.setrecursionlimit(10000000)
# # abc='abcdefghijklmnopqrstuvwxyz'
# # abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
# # words = {1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',14:'fourteen',15:'quarter',16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen',20:'twenty',21:'twenty one',22:'twenty two',23:'twenty three',24:'twenty four',25:'twenty five',26:'twenty six',27:'twenty seven',28:'twenty eight',29:'twenty nine',30:'half'}
# # vow=['a','e','i','o','u']
# # dx,dy=[0,1,0,-1],[1,0,-1,0]
#
# import random
from collections import deque, Counter, OrderedDict, defaultdict


# from math import ceil, floor, log, sqrt, factorial, pi, gcd, degrees, atan2
# from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
# mod, MOD = 1000000007, 998244353
# import queue


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def get_ints(): return map(int, sys.stdin.readline().strip().split())


def input(): return sys.stdin.readline().strip()


# from heapq import nsmallest, nlargest, heapify, heappop, heappush, heapreplace, _heapify_max, _heapreplace_max, \
# 	_heappop_max
n, m, k = get_ints()
a = []
for i in range(m + 1):
	a.append(int(input()))
cnt = 0
fed = a[-1]
for i in range(m):
	d = str(bin(a[i] ^ fed)).count('1')
	if (d <= k):
		cnt = cnt + 1
print(cnt)