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.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Formatter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main
{
	private static BufferedReader in;
	private static BufferedWriter out;
	private static int n;
	private static int m;
	private static int k;

	public static void main(String... args) throws IOException
	{
		// streams
		boolean file = false;
		if (file)
			in = new BufferedReader(new FileReader("input.txt"));
		else
			in = new BufferedReader(new InputStreamReader(System.in));
		out = new BufferedWriter(new OutputStreamWriter(System.out));
		// out = new BufferedWriter(new FileWriter("output.txt"));
		StringTokenizer tok;

		// take input
		tok = new StringTokenizer(in.readLine());
		n = Integer.parseInt(tok.nextToken());
		m = Integer.parseInt(tok.nextToken());
		k = Integer.parseInt(tok.nextToken());
		
		// read enemy
		boolean[][] army = new boolean[m][n];
		for (int i = 0; i < m; i++)
		{
			int x = Integer.parseInt(in.readLine());
			army[i] = toBoolean(x);
		}
			
		// read the dude
		boolean[] dude = toBoolean(Integer.parseInt(in.readLine()));
		
		// count friends
		int friends = 0;
		for (int i = 0; i < m; i++) 
		{
			int diff = 0;
			for (int j = 0; j < n; j++) 
			if (army[i][j] != dude[j])
				diff ++;
			if (diff <= k)
				friends ++;
		}
		System.out.println(friends);
			
			
	
		solve();

		out.flush();
	}

	private static boolean[] toBoolean(int x)
	{
		boolean result[] = new boolean[n];
		int idx = 0;
		for (int i = 0; i <= n; i++) 
		{
			if (x % 2 == 1)
				result[i] = true;
			x /= 2;
		}
		return result;
	}

	private static void solve()
	{
		// TODO Auto-generated method stub
		
	}

	
}