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
from math import sqrt

def write_to_stdout(res):
    sys.stdout.write('%d\n' % (res))

def read_input():
    n, m, k = [int (_) for _ in input().rstrip().split()]
    values = []
    for i in range(m+1):
        values.append(int(input()))
    return n, m, k, values

def get_masks(values, n):
    result = [bin(values[i])[2:] for i in range(n)]
    return result

def get_diff(mask, value):
    n_bits = max(len(mask), len(value))
    # print(mask, value, n_bits)
    mask, value = mask[::-1], value[::-1]
    if len(mask) < n_bits:
        mask += '0'*(n_bits-len(mask))
    if len(value) < n_bits:
        value += '0'*(n_bits-len(value)) 
    count = 0
    # print(mask, value, n_bits)
    for i in range(n_bits):
        if mask[i] != value[i]:
            count += 1
    return count
    
    
def get_answer(values, k):
    N = len(values) - 1
    masks = get_masks(values, N)
    ref_value = bin(values[-1])[2:]
    result = [get_diff(masks[i], ref_value) <= k for i in range(N)]
    return sum(result)
    
def main():
    n, m, k, values = read_input()
    answer = get_answer(values, k)
    write_to_stdout(answer)


    
    
if __name__ == '__main__':
    main()