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.*;

public class JavaApplication1 {
	public static void main(String[] args) 
        {
            
            int n,m,k,play=0;
            String fedor;
            Scanner in =new Scanner(System.in);
            n = in.nextInt();
            m = in.nextInt();
            k = in.nextInt();
            ArrayList<String> players = new ArrayList<>();
            for(int i=0;i<m;i++)
            {
                players.add(Conc(Integer.toBinaryString(in.nextInt()),n));
            }
            fedor = Conc(Integer.toBinaryString(in.nextInt()),n);
            for (String player : players) {
                int fals=0;
                Boolean flag=true;
                for(int s=0;s<n;s++)
                {
                    if(player.charAt(s)!=fedor.charAt(s))
                    {
                        fals++;
                    }
                    if(fals>k) {flag=false;break;}
                }
                if(flag)play++;
            }
            System.out.println(play);
        }
        public static String Conc(String te,int n)
        {
            String tee;
            if(te.length()>=n)
                {
                    te = te.substring(te.length() - n);
                }
                else
                {
                    tee="0";
                    for(int h=0;h<n-te.length()-1;h++)
                    {
                        tee+="0";
                    }
                    te=tee+te;
                }
            return te;
        }
}