People love to play CS in their free time. But many of them found it booring. So one of them thought to modify it a little.
The game has (m) players and n types of weapons. Weapons are numbered from 0 to (n-1) and the players from 1 to m.
Each player has a set of weapons which is described by a non-negative integer xi. If j-th bit of xi is 1 then the i-th player has a weapon of j-th kind.
Now your friend Steve Buyaka being new to the game seeks your help in identifying his friends. Two players are friends if their weapon compositions differ by at most k weapons.

Help Steve to count how many players are his friends.

Input

First line contains three integers n,m,k.
Next (m) lines contains a single integer xi, that describes i-th player weapons.
We remind you that Steve is the (m)-th player.

Output

Output a single integer denoting number of friends of Steve.

Constraints

(1<=k<=20)
(1<=n<=20)
(1<=m<=1000000)
(1<=xi<=1000000)