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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.sql.Struct;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class CF467B {
    public static void main(String[] args) {
        FastReader input = new FastReader();
        PrintWriter pw = new PrintWriter(System.out);

        int n = input.nextInt();
        int m = input.nextInt();
        int k = input.nextInt();

        String[] arr = new String[m+1];

        for(int i = 0;i <= m;i++){
            long info = input.nextLong();
            String s = Long.toBinaryString(info);
            arr[i] = s;
        }

        String t = arr[m];

        int count  = 0;

        for(int i = 0;i < m;i++){
            String curr = arr[i];

            if(t.length() != curr.length()){
                if(t.length() < curr.length()){
                    int diff = curr.length() - t.length();
                    String temp = new String();
                    for(int p = 1;p <= diff;p++)
                        temp += "0";

                    temp += t;
                    int missmatch = 0;
                    for(int j = 0;j < temp.length();j++){
                        if(temp.charAt(j) != curr.charAt(j))
                            missmatch++;
                    }
                    if(missmatch <= k)
                        count++;

                }
                else if(curr.length() < t.length()){
                    int diff = t.length() - curr.length();
                    String temp = new String();
                    for(int p = 1;p <= diff;p++)
                        temp += "0";

                    temp += curr;
                    int missmatch = 0;
                    try {
                        for(int j = 0;j < temp.length();j++){
                            if(temp.charAt(j) != t.charAt(j))
                                missmatch++;
                        }
                    }
                    catch (Exception e){
                        pw.println(temp + " "  + curr);
                    }

                    if(missmatch <= k)
                        count++;
                }
            }
            else{
                int missmatch = 0;
                for(int j = 0;j < curr.length();j++){
                    if(curr.charAt(j) != t.charAt(j)){
                        missmatch++;
                    }
                }
                if(missmatch <= k)
                    count++;
            }
        }
        pw.println(count);
        pw.flush();
        pw.close();
    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}