Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

B. Fedor and New Game

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter 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 *x*_{i}. Consider binary representation of *x*_{i}: if the *j*-th bit of number *x*_{i} 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 *x*_{i} (1 ≤ *x*_{i} ≤ 2^{n} - 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 04:06:42 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|