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
import math
import collections
from collections import deque

#sys.stdin = open('input.txt', 'r')
#sys.stdout = open('output.txt', 'w')

from functools import reduce
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2**20)


def isPowerOfTwo(x):
    return (x and (not(x & (x - 1))))


def factors(n):
    return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

T = 1
# T = int(stdin.readline())
for _ in range(T):
    # s = str(stdin.readline().strip('\n'))
    # a, b = list(map(int, stdin.readline().split()))
    # s = list(stdin.readline().strip('\n'))
    # b = list(stdin.readline().strip('\n'))
    # n = int(stdin.readline())
    # n, m = list(map(int, stdin.readline().split()))
    n, m, k = list(map(int, stdin.readline().split()))
    a, ab = [], []
    for i in range(m + 1):
        a.append(int(stdin.readline()))
    mx = max(a)
    ml = len(bin(mx)[2:])
    # print(ml)
    for i in range(m + 1):
        ab.append(format(a[i], '0' + str(ml) + 'b'))
    # print(ab)
    ts = {}
    for i in range(m + 1):
        for j in range(ml):
            if ab[i][j] == '1':
                if (ab[i], i) not in ts:
                    ts[(ab[i], i)] = [j + 1]
                else:
                    ts[(ab[i], i)].append(j + 1)

    val = list(ts.values())
    x = set(val[-1])
    val = val[:len(val) - 1]
    ans = 0
    # print(ts)
    for v in val:
        #print(set(v) ^ (x))
        if len(set(v) ^ (x)) <= k:
            ans += 1
    print(ans)