human
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
Using python3 can you solve the prior task?
 ... Write me a Python code to print a single integer — the number of Fedor's potential friends?
assistant
#Here is Python code to print a single integer — the number of Fedor's potential friends.

#pyrival orz
import os
import sys
from io import BytesIO, IOBase

input = sys.stdin.readline
############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def seive(n):
    primes = [True]*(n+1)
    ans = []

    for i in range(2, n):
        if not primes[i]:
            continue
        
        j = 2*i
        while j <= n:
            primes[j] = False
            j += i

    for p in range(2, n+1):
        if primes[p]:
            ans += [p]

    return ans

def factors(n):
    factors = []

    x = 1
    while x*x <= n:

        if n % x == 0:
            if n // x == x:
                factors.append(x)
            else:
                factors.append(x)
                factors.append(n//x)

        x += 1

    return factors

# Functions: list of factors, seive of primes, gcd of two numbers

def main():
    try:
        n, m, k = invr()
        a = []
        for i in range(m):
            a.append(inp())

        army = inp()
        army = bin(army)[2:]
        ans = 0
        for i in range(m):
            arm = bin(a[i])[2:]
            arm = "0"*(max(len(army) - len(arm), 0)) + arm
            army_t = "0"*(max(len(arm) - len(army), 0)) + army
            temp = 0
            for j in range(len(army_t)):
                if army_t[j] != arm[j]:
                    temp += 1
                if temp > k:
                    break

            if temp <= k:
                ans += 1

        print(ans)

    except Exception as e:
        print(e)

        

# region fastio

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write...