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:
/*to solve feder problem*/
import java.util.*;
import java.lang.*;
import static java.lang.Math.*;

public class cf3
{
	public static void main(String args[])
	{
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt(),m=scan.nextInt(),k=scan.nextInt(),i,fb,friend=0;
		Integer []a=new Integer[m+1];
		//GetBinary g1=new GetBinary();
		//GetBinary g=new GetBinary();
		for(i=0;i<m+1;i++)
		{
			//a[i]=0;
			a[i]=scan.nextInt();
			//GetBinary g=new GetBinary(a[i]);
			//a[i]=g.GetBinary(a[i]);
			//a[i]=g.bn;
			//System.out.print(a[i]+" ");
			
		}
		for(i=0;i<m+1;i++)
		{
			//a[i]=g.getBinaryNumber(a[i]);
			//System.out.print(a[i]+" ");
		}
		//fb=abs(g1.findBit(a[m]));
		/*while(a[m]!=0)
		{
			if(a[m]%10==1)
			{
				fb++;
			}
			a[m]=a[m]/10;
		}*/
		for(i=0;i<m;i++)
		{
			//System.out.println("bit="+abs(g1.findBit(a[i])));
			//System.out.println("diff="+abs(fb-g1.findBit(a[i])));
			
			//if(abs(fb-g1.findBit(a[i]))<=k)
			if(Integer.bitCount(a[i] ^ a[m]) <=k) 
			{
				friend++;
			}
		}
		System.out.print(friend);
	}
}
class GetBinary
{
	int sum,bn=0,mul=1,rem;
	GetBinary()
	{
		
	}
	GetBinary(int dn)
	{
		//bn=0;
		while(dn!=0)
		{
			rem=dn%2;
			bn=bn+mul*rem;
			mul=mul*10;
			dn=dn/2;
		}
		//return bn;
	}
	int findBit(int n)
	{
		int bit1=0;
		while(n!=0)
		{
			if(n%10==1)
			{
				bit1++;
			}
			n=n/10;
		}
		return bit1;
	}
	//return bn;
}