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.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;

import javax.print.attribute.standard.MediaSize.ISO;

public class Codeforces2 implements Runnable {

  private BufferedReader br = null;
  private PrintWriter pw = null;
  private StringTokenizer stk = new StringTokenizer("");

  public static void main(String[] args) {
    new Thread(new Codeforces2()).run();
  }

  public void run() {

    /*
     * try { br = new BufferedReader(new FileReader("/home/user/freshdb.sql")); pw = new
     * PrintWriter("/home/user/freshdb_fix.sql"); } catch (FileNotFoundException e) {
     * e.printStackTrace(); }
     */

    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new OutputStreamWriter(System.out));
    solver();
    pw.close();

  }

  private void nline() {
    try {
      if (!stk.hasMoreTokens())
        stk = new StringTokenizer(br.readLine());
    } catch (IOException e) {
      throw new RuntimeException("KaVaBUnGO!!!", e);
    }
  }

  private String nstr() {
    while (!stk.hasMoreTokens())
      nline();
    return stk.nextToken();
  }

  private int ni() {
    return Integer.valueOf(nstr());
  }

  private long nl() {
    return Long.valueOf(nstr());
  }

  private double nd() {
    return Double.valueOf(nstr());
  }

  String nextLine() {
    try {
      return br.readLine();
    } catch (IOException e) {
    }
    return null;
  }

  class Point {
    int x;
    int y;

    Point(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }

  private void bfs(int t, boolean[] using, int[][] g) {
    Stack<Integer> st = new Stack<Integer>();
    int n = using.length;
    st.add(t);
    while (!st.empty()) {
      int p = st.pop();
      for (int i = 0; i < n; i++) {
        if (g[p][i] == 1 && !using[i]) {
          st.add(i);
          using[i] = true;
        }
      }
    }
  }

  public int gcd(int a, int b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }

  private boolean checkPrime(int a) {
    for (int i = 2; i <= Math.sqrt(a); i++) {
      if (a % i == 0)
        return false;
    }
    return true;
  }

  private void solver() {
    int n = ni(), m = ni(), k = ni();
    ArrayList<String> ar = new ArrayList<String>();
    for(int i=0; i<m+1; i++){
      ar.add(toLen(nbi().toString(2), n));
    }
    int ans = 0;
    for(int i=0; i<m; i++){
      int dif = 0;
      for(int j=0; j<n; j++){
        if (ar.get(i).charAt(j)!=ar.get(m).charAt(j)){
          ++dif;
        }
      }
      if (dif <= k)
        ans++;
    }
    System.out.println(ans);
  }

  private String toLen(String s, int n){
    int t = n-s.length();
    for(int i=0; i<t; i++){
      s = "0"+s;
    }
    return s;
  }


  private BigInteger nbi() {
    return new BigInteger(nstr());
  }

  void exit() {
    pw.close();
    System.exit(0);
  }

}