In a virtual game, there are m players, having atmost n attributes each. Types of attributes are numbered from 0 to n-1. Each player is assigned a non-negative integer x_i. Consider binary representation of x_i: if the j-th bit of number x_i is equal to one, then the i-th player has attribute of the j-th type.

Sahith (an outsider boy) wants to make friends in this virtual game. Here, two players can become friends if their attributes differ in at most k types of attributes. Help Sahith count how many players among m players can become his friends.

For Example: For k==2, player 1 has attributes of types 1, 2 and 3, and Sahith has attributes of types 1, 2, 3, 4 and 5. Then player 1 and sahith can become friends as the number of attributes differ in 2 types only i.e. 4th and 5th attribute.

Input:

The first line contains three space seperated integers ,n, m and k (1 ≤ k ≤ n ≤ 20; 1 ≤ m ≤ 1000).

The i-th line of the next m lines contains a single integer x_i (0 ≤ x_i ≤ 2ⁿ - 1), representing the i-th player's attributes. 

The next line contains an integer s(0<=s<=2ⁿ-1) representing Sahith's attributes

Output:

Print a single integer — the number of Sahith's potential friends.