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.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;



public class Main {
    
    public static void main(String[] args) throws FileNotFoundException {
        Buffered io = new Buffered(System.in);
        int n, m, k, counter = 0;
        n = io.nextInt();
        m = io.nextInt();
        k = io.nextInt();
        
        long[] x = new long[m+2];
        for (int i = 1; i < m+2; i++)
            x[i] = io.nextLong();

        String b1 = DecToBin(x[m+1]);
        
        for(int i = 1;i<m+1;i++)
            if(numberOfDiffers(x[i], b1)<=k)
                counter++;
        System.out.println(counter);
    }
    
    private static int numberOfDiffers(long a, String b1){
        int counter = 0;
        String a1 = DecToBin(a);
        int i = 0;
        for(i = 0;i<Math.min(a1.length(), b1.length());i++)
            if(a1.charAt(i)!=b1.charAt(i))
                counter++;
        if(a1.length()>b1.length()){
            for (int j = i; j < a1.length(); j++){ 
                if(a1.charAt(j)=='1'){
                    counter++;
                }
            }
        }
        else if(b1.length()>a1.length()){
            for (int j = i; j < b1.length(); j++){ 
                if(b1.charAt(j)=='1'){
                    counter++; 
                }
            }
        }
        return counter;
    }
    
    private static String DecToBin(long number)
    {
        if ( number == 0 ) return "0";
        if ( number == 1 ) return "1";

        if ( number % 2 == 0 )
            return "0"+DecToBin(number / 2);
        else
            return "1"+DecToBin(number / 2);
    }
    
    public static class Buffered
    {
        private BufferedReader reader;
        private StringTokenizer tokenizer;
        private PrintWriter writer;
        
        public Buffered(InputStream stream) throws FileNotFoundException 
        {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer= null;
            writer=new PrintWriter(System.out);
        }
        
        public boolean hasNext()
        {
            while(tokenizer==null || !tokenizer.hasMoreTokens())
            {
                try{
                    String line = reader.readLine();
                    if(line==null) return false;
                    tokenizer = new StringTokenizer(line);
                }
                catch(IOException e)
                {
                    throw new RuntimeException();
                }
            }
            return tokenizer.hasMoreTokens();
        }
        
        public String next()
        {
            while(tokenizer==null || !tokenizer.hasMoreTokens())
            {
                try{
                    tokenizer = new StringTokenizer(reader.readLine());
                }
                catch(IOException e)
                {
                    throw new RuntimeException();
                }
            }
            return tokenizer.nextToken();
        }
        
        public int nextInt()
        {
            return Integer.parseInt(next());
        }
        
        public long nextLong()
        {
            return Long.parseLong(next());
        }
        
        public void println(String x)
        {
            writer.print(x);
            writer.flush();
        }
    }
}