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

public class B467{
	public static void main(String[] args){
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
		final long start = System.currentTimeMillis();
		new Task1().solve(in, out);
		final long duration = System.currentTimeMillis()-start;
		out.close();
	}

	static class Task1{
		public void solve(InputReader in, PrintWriter out){
			int n=in.nextInt(), m=in.nextInt(), k=in.nextInt();
			String zeros = "00000000000000000000";
			String[] army = new String[m];
			for(int i=0; i<m; i++){
				army[i] = Integer.toBinaryString(in.nextInt());
				army[i] = zeros.substring(0, n-army[i].length())+army[i];
			}
			String fedor = Integer.toBinaryString(in.nextInt());
			fedor = zeros.substring(0, n-fedor.length())+fedor;

			int ans=0;
			for(int i=0; i<m; i++){
				if(check(fedor, army[i], n, k)){
					ans++;
				}
			}
			out.println(ans);
		}

		boolean check(String fedor, String army, int n, int k){
			for(int i=0; i<n; i++){
				if(fedor.charAt(i)!=army.charAt(i)) k--;
				if(k<0) return false;
			}
			return true;
		}
	}

	static class InputReader{
		private BufferedReader reader;
		private StringTokenizer tokenizer;
		
		public InputReader(){
			reader = new BufferedReader(new InputStreamReader(System.in));
			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 (int)Integer.parseInt(next());
		}

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

		public double nextDouble(){
			return (double)Double.parseDouble(next());
		}

		public String nextLine(){
			String s = null;
			try{
				s = reader.readLine();
			} catch(Exception e){
				throw new RuntimeException(e);
			}
			return s;
		}
	}
}