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:
/////archit kumar
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.math.*;

public class main {
    

    static int n,inn,m,k;
    static int friend = 0;
    static int pw =(int) Math.pow(2, 20);
       static  int bn1[]=new int[pw-1];
    public static void main(String[] args) throws IOException,NumberFormatException
    {
        
        try
        {
        Scanner sc = new Scanner(System.in);
         n = sc.nextInt();
         m = sc.nextInt();           //archit
         k = sc.nextInt();
         int v[] = new int[m+2];
         for(int i=1;i<=m+1;i++)
        v[i]=sc.nextInt();
      
          int bn2[]=new int[pw-1];
           ArrayList a = new ArrayList();
            a=binary(v[m+1],n);
           int l=0;
           for(Object o:a)
           {
             bn1[l]=(int)o;
             l++;
           }
          
           
           
           for(int i=1;i<m+1;i++)
        {    
             a=binary(v[i],n);
             l=0;
               for(Object o:a)
               {
                 bn2[l]=(int)o;
                 l++;
               }
               
            compare( bn2);   
        }  
        System.out.println(friend);
      
        }
        catch(Exception e)
        {
            System.out.println(e.getMessage());
        }
    }
 public  static ArrayList binary(int in,int n)
    {
        ArrayList a= new ArrayList();
       inn=in;
          for(int i=0;i<n;i++)
        {
            if((inn)!=0)
            {
             
             a.add(inn%2);
            }
            else
            {
            
            a.add(0);
            }
            if(inn!=1)
            {
            inn = (inn/2);
            
            }
            else
            {
             inn=0;
            
            }
        }
          return a;
    }
   
  public static void compare(int bn3[])
   {
    int diff=0;
            for(int y=0;y<n;y++)
       {
           if(bn1[y]!=bn3[y])
               diff++;
           
       }
       if(diff<=k)
           friend++;
      
       
    
   }
    
}