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 JAVA):

Solution:
/* Harish Anumula  */
import java.util.*;
import java.io.*;
//import java.math.*;

public class MAXEINSTLE
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
        FastScanner scan = new FastScanner(br);
        Task solver = new Task();
        solver.solve(scan,pw);
        pw.close();
    }
}



class Task{
    public void solve(FastScanner scan , PrintWriter pw) throws java.lang.Exception{
        int n = scan.nextInt();
        int m = scan.nextInt();
        int k = scan.nextInt();
        int arr[] = new int[m+1];
        for(int i = 0;i<=m;i++){
            arr[i] = scan.nextInt();
        }
        int ans = 0;
        for(int i = 0;i<m;i++){
            if(Integer.bitCount(arr[i]^arr[m]) <= k){
                ans++;
            }
        }
        pw.println(ans);
    }
}



class FastScanner {

    BufferedReader br;
    StringTokenizer st;

    public FastScanner(BufferedReader br) {
        this.br = br;
    }

    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
    public String nextString() throws Exception {
        return br.readLine();
    }
}