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.util.Arrays;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class MainClass {
    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;
        }
    }
    static String addZeros (int add)
    {
        char [] chars = new char[add];
        Arrays.fill(chars,'0');
        return new String(chars) ;
    }
    public static void main(String[] args)  {
        FastReader in = new FastReader() ;
        int numberOfTypes , playerCount , maxDiffer , ans = 0 ;
        numberOfTypes = in.nextInt() ;
        playerCount = in.nextInt() ;
        maxDiffer = in.nextInt() ;
        String armyTypes [] = new String[playerCount+1] ;
        for (int i = 0 ; i <= playerCount ; i++)
        {
            int input = in.nextInt() ;
            armyTypes[i] = Integer.toBinaryString(input);
        }
        int count , len ;
        for (int i = 0 ; i < playerCount ; i++)
        {
            len = armyTypes[playerCount].length()-armyTypes[i].length() ;
            if (len > 0)
            {
                armyTypes[i] = addZeros(len) + armyTypes[i] ;
            }
            else if (len < 0)
            {
                armyTypes[playerCount] = addZeros(len*(-1)) + armyTypes[playerCount] ;
            }
            count = 0 ;
            for (int j = 0  ;j < armyTypes[i].length() ; j++)
            {
                if (armyTypes[i].charAt(j) != armyTypes[playerCount].charAt(j))
                {
                    count++ ;
                }
            }
            if (count <= maxDiffer)
                ans++ ;
        }
        System.out.println(ans);







    }
}