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.awt.List;
import java.math.MathContext;
import java.sql.Time;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Locale;
import java.util.Scanner;

import javax.swing.DefaultListModel;


public class MainTest
{
    static void print(int a[])
    {
        for(int i=0;i<a.length;i++) System.out.print(a[i]+" ");
        System.out.println();
    }
    static void print(long a[])
    {
        for(int i=0;i<a.length;i++) System.out.print(a[i]+" ");
        System.out.println();
    }
    static void println(int a[])
    {
        for(int i=0;i<a.length;i++) System.out.println(a[i]+" ");
    }
    
    static int sum(int []a)
    {
        int res=0;
        for(int i=0;i<a.length;i++) res+=a[i];
        return res;
    }
    static long[] getSimple(int from,int to)
    {
        long a[]=new long[to-from];
        for(int i=0;i<a.length;i++) a[i]=from+i;
        //print(a);
        int sum=0;
        for(int i=0;i<a.length;i++)
        {
            if(a[i]>0)
            {
                for(int j=i+1;j<a.length;j++) if(a[j]%a[i]==0) a[j]=0;
                sum++;
            }
        }
        long b[]=new long[sum];
        sum=0;
        for(int i=0;i<a.length;i++) if(a[i]>0) {b[sum]=a[i]; sum++;}
        //System.out.println("SIMPLE!");
        print(b);
        return b;
    }
    static int check(int a)
    {
        if(a==1) return 0;
        else return 1;
    }
    static int[] inverse(int []a, int x,int y)
    {
        int b[]=new int[a.length];
        for(int i=0;i<a.length;i++)
        {
            if(i>=x&&i<=y)
            {
                if(a[i]==1) b[i]=0;
                else b[i]=1;
                continue;
            }
            b[i]=a[i];
        }
        return b;
    }
    static long sum(long a)
    {
        long res=0;
        for(int i=1;i<=a;i++) res+=i;
        return res;
    }
    //static int a[];
    public static void main(String args[])
    {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int k=in.nextInt();
        int a[]=new int[m];
        for(int i=0;i<m;i++) a[i]=in.nextInt();
        int b=in.nextInt();
        int res=0;
        for(int i=0;i<m;i++)
        {
            int t=b;
            int sum=0;
            while(true)
            {
                int ai;
                int ti;
                if(a[i]==0) ai=0;
                else if(a[i]==1) {ai=1; a[i]=0;}
                else {ai=a[i]%2; a[i]=a[i]/2;}
                if(t==0) ti=0;
                else if(t==1) {ti=1; t=0;}
                else {ti=t%2; t=t/2;}
                if(ti!=ai) sum++;
                if(sum>k) break;
                if(a[i]==0&&t==0) break;
            }
            if(sum<=k) res++;
        }
        System.out.println(res);
    }
}