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.*;
import java.lang.*;
import java.math.*;
public class FedorAndNewGame {
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        String[] ints = sc.nextLine().split(" ");
        int soldierTypes = Integer.parseInt(ints[0].trim());
        int numPlayers = Integer.parseInt(ints[1].trim())+1;
        int k = Integer.parseInt(ints[2].trim());
        
        int[] playerArmy = new int[numPlayers];
        for(int i=0;i<numPlayers;i++){
            playerArmy[i] = Integer.parseInt(sc.nextLine().trim());
        }
        
        int numFriends=0;
        for(int i=0;i<numPlayers-1;i++){
            String player_i_bin = Integer.toBinaryString(playerArmy[i]);
            String fedor_bin = Integer.toBinaryString(playerArmy[numPlayers-1]);
            int diff = findBitsDifference(player_i_bin,fedor_bin,soldierTypes);
            if(diff<=k)numFriends++;
        }
        
        System.out.println(numFriends);
    }
    
    public static int findBitsDifference(String binary1, String binary2,int n){
        int binary1Length=binary1.length();
        int binary2Length=binary2.length();
        if(binary1Length>binary2Length){
            for(int i=0;i<(binary1Length-binary2Length);i++){
                binary2 = "0"+binary2;
            }
        }
        else if(binary2Length>binary1Length){
            for(int i=0;i<(binary2Length-binary1Length);i++){
                binary1 = "0"+binary1;
            }
        }
        if(binary1.length()>n)binary1 = binary1.substring(0, n);
        if(binary2.length()>n)binary2 = binary2.substring(0, n);
        int diff=0;
        for(int i=0;i<binary1.length();i++){
            if(binary1.charAt(i)!=binary2.charAt(i)){
                diff++;
            }
        }
        return diff;
    }
    
}