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.*;
import java.util.*;

public class Fedor {
	static class Task {
		
		public void solve(InputReader in, PrintWriter out) {
    		int N = in.nextInt();
    		int M = in.nextInt();
    		int K = in.nextInt();
    		int[][] players = new int[M+1][N+1];
    		for(int i=0; i<M+1; i++) {
    			int hello = in.nextInt();
    			/*String value = Integer.toBinaryString(hello);
    			out.println(hello + " " + value);
    			out.println(Integer.toBinaryString(8));
    			String[] a = value.split("");
    			*/
    			for(int j=0; j<N; j++) {
    				int hello2 = hello/2;
    				players[i][j] = hello-(hello2*2); //Integer.parseInt(a[j]);
    				hello=hello2;
    			}
    			
    		}
    		for(int i=0; i<N; i++) {
    			for(int j=0; j<M; j++) {
    				if(players[j][i] != players[M][i]) {
    					players[j][N]++;
    				}
    			}
    		}
    		int result=0;
    		for(int i=0; i<M; i++) {
    			if(players[i][N]<=K) {
    				result++;
    			}
    		}
    		out.println(result);
    	}
    }

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}