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:
import java.io.*;
import java.util.*;

public class PrB {
    private void run() {
        Locale.setDefault(Locale.US);
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }

        if (oj) {
            in = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                in = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException e) {
                MLE();
            }
        }
        Solver s = new Solver();
        s.in = in;
        s.out = out;
        s.solve();
        if (!oj) {
            err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
            err.printf("Mem: %d\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20);
        }
        out.flush();
    }

    public static void MLE() {
        int[][] arr = new int[1024 * 1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024 * 1024];
        }
    }

    public static void main(String[] args) {
        new PrB().run();
    }

    long timeBegin = System.currentTimeMillis();
    FastScanner in;
    PrintWriter out;
    PrintStream err = System.err;

    class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStreamReader reader) {
            br = new BufferedReader(reader);
            st = new StringTokenizer("");
        }

        String next() {
            while (!st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException ex) {
                    PrB.MLE();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }


    class Solver {

        FastScanner in;
        PrintWriter out;
        PrintStream err = System.err;

        void func(long a,long b,long n){
            long s = a*b;
            if (s>=n){
                out.println(s);
                out.print(a);
                out.print(" ");
                out.print(b);
                return;
            }
            if (a>b)
                func(a,b+1,n);
            else
                func(a+1,b,n);


        }

        void solve(){

            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            long[] x = new long[m+2];
            for (int i = 1;i<=m+1;i++)
                x[i] = in.nextInt();

            int res = 0;
            int num;
            for (int i = 1;i<=m;i++){
                res++;
                num = 0;
                for (int j=0;j<n;j++){
                    if (((x[i]>>j)&1)!=((x[m+1]>>j)&1))
                        num++;
                    if (num>k){
                        res--;
                        break;
                    }

                }
            }

            out.println(res);

        }
    }

}