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 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

Difficulty: interview

Starter code:

Solutions:
def check(i):
    x, counter = armies[i] ^ armies[-1], 0
    while x:
        counter += x & 1
        x >>= 1
    return counter <= k

n, m, k = list(map(int, input().split()))
armies = [int(input()) for x in range(m + 1)]
print(sum(map(check, list(range(m)))))


n,m,k = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
fedya = int(input())
fedya = str(bin(fedya)[2:])
fedya = '0'*(n-len(fedya))+fedya
ans = 0
for bb in a:
    bbb = str(bin(bb)[2:])
    bbb = '0'*(n-len(bbb))+bbb
    delta = 0
    for i in range(n):
        if bbb[i]!=fedya[i]:
            delta+=1
    if delta<=k:
        ans+=1
print(ans)

def f(n, a, b):
    cnt = 0
    now = 1
    for i in range(n):
        if a & now == b & now:
            cnt += 1
        now *= 2
    return cnt
n, m, k = map(int, input().split())
a = []
for i in range(m + 1):
    a.append(int(input()))
ans = 0
for i in range(m):
    if f(n, a[i], a[m]) >= n - k:
        ans += 1
print(ans)

n,m,k = [int(x) for x in input().split()]
arr = [int(input()) for i in range(m+1)]

def calc(x):
	return bin(x^arr[-1]).count('1')<=k
print(sum(map(calc,arr[:-1])))

n,m,k=map(int,input().split())
a=[]
ans=0
for i in range(m):
    a.append(int(input()))
s=int(input())
r=[]
for i in range(n):
    r.append(s%2)
    s=s//2
for i in range(m):
    j=0
    c=0
    g=a[i]
    while j<n and c<=k:
        if r[j]==g%2:
            j+=1
        else:
            j+=1
            c+=1
        g=g//2
    if c<=k:
        ans+=1
print(ans)

n, m, k = [int(_) for _ in input().split(" ")]

p = [int(input()) for i in range(0, m+1)]
fd = p[-1]
ans = 0
for x in iter(p[:-1]):
    t = x ^ fd
    cnt = 0
    while t:
        if t % 2 == 1:
            cnt += 1
        t = t >> 1
    if cnt <= k:
        ans += 1
print (ans)


def dif(x, y):
    c = 0
    while x != 0 or y!= 0:
        if x % 2 != y % 2:
            c += 1
        x //= 2
        y //= 2
    return c

n, m, k = map(int, input().split())
x = [int(input()) for i in range(m + 1)]
cnt = 0
for i in range(m):
    if dif(x[i], x[m]) <= k:
        cnt += 1
print(cnt)

n, m, k = [int(i) for i in input().split()]
values = []
for i in range(m):
	values.append(int(input()))
count = 0
p = int(input())
for value in values:
	if bin(p ^ value).count('1') <= k:
		count += 1
print(count)



v=list(int(x) for x in input().split())
n=v[0]
m=v[1]
k=v[2]
v=list()
for i in range (m+1):
    v.append(int(input()))
f=bin(v[m])[2:]
f=('0'*(n-len(f)))+f
tot=0
for i in range(m):
    c=0
    t=bin(v[i])[2:]
    t=('0'*(n-len(t)))+t
    #print (bin(v[i]), t,f)
    for j in range (n):
        if t[j]!=f[j]:
            c+=1
    if  c<=k:
        tot+=1
print(tot)

n,m,k = list(map(int,input().split()))
a,c = [],0
for i in range(m+1):
    a.append(bin(int(input())).replace('0b',''))
for i in range(m):
    s = str(int(a[m]) + int(a[i]))
    if s.count('1') <= k:
        c += 1
print(c)
        


n,m,r = map(int,input().split())
a = []
for i in range(m+1):
    s = bin(int(input()))[2:]
    t = str()
    for i in range(21 - len(s) + 1):
        t += '0'
    a.append(t + s)

res = 0
t = a[len(a)-1]
for i in range(len(a)-1):
    ans = 0
    for k in range(len(t)):
        if t[k] != a[i][k]:
            ans += 1
    if ans <= r:
        res += 1
print(res)

n,m,k = map(int, input().split())
arr = []
for _ in range(m+1):
	arr.append(int(input()))
lol = arr[m]
res = 0

for i in range(m):
	tmp = 0
	for j in range(n+1):
		if((lol^arr[i])&(2**j)!=0):
			tmp+=1
	if(tmp<=k):
		res+=1
print(res)

def count_one(n):
    c = 0
    while(n):
        n = n&(n-1)
        c = c + 1
    return c
nmk=input()
b=nmk.split(' ')
n=int(b[0])
m=int(b[1])
k=int(b[2])
a=[]
for i in range(m+1):
    istr=input()
    a.append(int(istr))
ans=0
for i in range(m):
    if(count_one(a[i]^a[m])<=k):
        ans=ans+1
print(ans)


def getdiff(a, b):
	return sum([a[i] != b[i] for i in range(n)])


n, m, k = list(map(int, input().split()))

armies = [0 for i in range(m)]
for i in range(m):
	armies[i] = (bin(int(input()))[2:]).rjust(n, '0')

ans = 0
M = (bin(int(input()))[2:]).rjust(n, '0')
for i in range(m):
	if getdiff(M, armies[i]) <= k:
		ans += 1
print(ans)


n, m, k = map(int, input().split())
a = list([])
for i in range(m + 1):
    l = int(input())
    a.append(l)
ans = 0
for i in range(m):
    bi = a[i] ^ a[m]
    s = bin(bi)
    r = 0
    j = 2
    while r <= k and j < len(s):
        if s[j] == '1':
            r += 1
        j += 1
    if r <= k:
        ans += 1
print(ans)

def pad(inp,num):
    while len(inp)<num:
        inp = '0' + inp
    return inp

inp = input().split(' ')
players = []
for x in range(int(inp[1])+1):
    players.append(pad(bin(int(input()))[2:],int(inp[0])))
fedor = players.pop()
output = 0
for player in players:
    diff = 0
    for b in range(len(fedor)):
        if fedor[b] != player[b]:
            diff += 1
    if diff <= int(inp[2]):
        output += 1
print(output)


n, m, k = map(int, input().split())
s = 0
a = []
for i in range(m + 1):
    a.append(int(input()))
p = a[m]
for i in range(m):
    d = list(map(int, list(bin(a[i] ^ p)[2:])))
    if sum(d) <= k:
        s+=1
        #print(a[i])
print(s)

def main():
    n, m, k = list(map(int, input().split()))

    a = []
    for _ in range(m):
        a.append(int(input()))
        
    f = int(input())
    
    def bitcnt(i):
        c = 0
        while i:
            i &= i - 1
            c += 1
        return c

    res = 0
    for ai in a:
        if bitcnt(ai ^ f) <= k:
            res += 1
    print(res)


def __starting_point():
    main()


__starting_point()

def cmp(s1, s2):
    ans = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            ans += 1
    return ans


n, m, k = map(int, input().split())
P = [bin(int(input()))[2:].rjust(n, "0") for i in range(m)]
Feda = bin(int(input()))[2:].rjust(n, "0")
ans = 0
for a in P:
    if cmp(Feda, a) <= k:
        ans += 1
print(ans)

def byte_v(a, n):
    ans = []
    while a != 0:
        ans.append(a % 2)
        a //= 2
    ans.reverse()
    
    ans = (n - len(ans))  * [0] + ans

    return ans


n, m, k = map(int, input().split())
players = []
for i in range(m + 1):
    curr_army = int(input())
    players.append(list(byte_v(curr_army, n)))
phill = players[-1]
ans = 0
for i in range(m):
    curr = 0
    
    for j in range(n):
        if phill[j] != players[i][j]:
            curr += 1
    if curr <= k:
        ans += 1
print(ans)

n, m, k = list(map(int,input().split()))
x = []
for i in range(m+1):
    x.append(int(input()))
fedor = x[m]
ans = 0
for i in range(m):
    fr = x[i]
    fed = fedor
    count = 0
    while fr > 0 or fed > 0:
        count += (fr%2 + fed%2) % 2
        fr //= 2
        fed //= 2
    if count <= k:
        ans += 1
print(ans)


def dif(a, b):
    b,a,ans=max(a,b),min(a,b),0
    c,d=[],[]
    i=0
    while a>0:
        if a%2==1:
            c.append(1)
        else:
            c.append(0)
        a//=2
        i+=1
    i=0
    while b>0:
        if b%2==1:
            d.append(1)
        else:
            d.append(0)
        b//=2
    for i in range(len(c)):
        if c[i]!=d[i]:
            ans+=1
    for i in range(len(c),len(d)):
        if d[i]==1:
            ans+=1
    return ans
n,m,k = map(int,input().split())
ans=0
x=[]
for i in range(m+1):
    x.append(int(input()))
for i in range(m):
    if dif(x[i], x[m])<=k:
        ans+=1
print(ans)

n, m, k = [int(x) for x in input().split()]
arr = []
o = 0
for i in range(m):
    arr.append(int(input()))
f = int(input())
f2 = []
for i in range(n -1, -1, -1):
    if (2 ** i) <= f:
        f -= (2 ** i)
        f2.append(True)
    else:
        f2.append(False)
for i in arr:
    z = 0
    for j in range(n - 1, -1, -1):
        if 2 ** j <= i:
            i -= 2 ** j
            if not f2[n - 1 - j]:
                z += 1
        else:
            if f2[n - j - 1]:
                z += 1
    if z <= k:
        o += 1
print(o)

import math
n,m,k = list(map(int,input().split()))
lst = [0]*m
res = [0]*m
ans = 0
otvet = 0
for i in range(m):
    lst[i] = int(input())
    #lst[i] = bin(lst[i])[2:]

fed = int(input())
#fed = bin(fed[2:])
for i in range(m):
    res[i] = lst[i] ^ fed
    res[i] = bin(res[i])[2:]
    ans = 0
    for j in range(len(res[i])):

        if res[i][j] == '1':
            ans+=1

    if ans<=k:

         otvet+=1
print(otvet)


def diff(a,b):
    while(len(a)<len(b)):
        a="0"+a
    while(len(b)<len(a)):
        b="0"+b
    ret=0
    for i in range(len(a)):
        if(a[i]!=b[i]):
            ret+=1
    return ret

n,m,k=list(map(int,input().split()))
L=[]
for i in range(m):
    x=int(input())
    L.append(bin(x)[2:])
s=bin(int(input()))[2:]

ans=0
for i in range(m):
    z=diff(L[i],s)
    if(z<=k):
        ans+=1
print(ans)