Polycarpus loves lucky numbers. Everybody knows that lucky numbers are positive integers, whose decimal representation (without leading zeroes) contain only the lucky digits *x* and *y*. For example, if *x* = 4, and *y* = 7, then numbers 47, 744, 4 are lucky.

Let's call a positive integer *a* undoubtedly lucky, if there are such digits *x* and *y* (0 ≤ *x*, *y* ≤ 9), that the decimal representation of number *a* (without leading zeroes) contains only digits *x* and *y*.

Polycarpus has integer *n*. He wants to know how many positive integers that do not exceed *n*, are undoubtedly lucky. Help him, count this number.
The first line contains a single integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">9</sup>) — Polycarpus's number.
'''
# Feder and new game
n,m,k = map(int,input().split())
li=[]
for i in range(m+1):
    li.append(int(input()))
out = 0
for i in range(m):
    xor = bin(li[i]^li[-1])[2:]
    if xor.count("1")<=k:
        out+=1
print(out)
    
'''
lis = []
for i in range(0,10):
    for j in range(0,10):
        for k in range(0,10):
            for l in range(0,2**k):
                b = bin(l)[2:]
                b = b.zfill(k)
                b = b.replace("0",str(i))
                b = b.replace("1",str(j))
                lis.append(int(b))
count = 0
lis = set(lis)
a = int(input())
for m in lis:
    if int(m)<=a:
        count+=1
if a==10**9:
    print(count)
else:
    print(count-1)
