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.util.Scanner;
public class A { 
		    public static void main(String[] args) {
		      Scanner sc=new Scanner(System.in);
		      int n=sc.nextInt();
		      int m=sc.nextInt();
	          int k=sc.nextInt();
	          String s[]=new String[m+1];
	          
	          for(int i=0;i<m+1;i++){
	        	  int a=sc.nextInt();
	        	 s[i]=Integer.toBinaryString(a);
	          }
	          String s1=s[m];
	          int count=0,c=0;
	          for(int i=0;i<m;i++){	c=0;      
	          String s2="";
	          String s3="";
	          if(s1.length()>=s[i].length()) { s2=s1.substring(s1.length()-s[i].length(),s1.length()); s3=s1.substring(0, s1.length()-s[i].length()); }
	          else if(s[i].length()>s1.length()) { s2=s[i].substring(s[i].length()-s1.length(), s[i].length()); s3=s[i].substring(0, s[i].length()-s1.length()); }
	            for(int l=0;l<s3.length();l++) if(s3.charAt(l)=='1') c++;  
	            for(int j=s2.length()-1;j>=0;j--){	   
	            	 if(s1.length()>=s[i].length() && s2.charAt(j)!=s[i].charAt(j)) c++;
	            	 if(s[i].length()>s1.length() && s2.charAt(j)!=s1.charAt(j)) c++;
	            	}
	            if(c<=k) count++;
	          }
	          System.out.println(count);
    }
}