very-cool-numbers

For a number X, let its "Coolness" be defined as the number of "101"s occurring in its binary representation. For example, the number 21 has Coolness 2, since its binary representation is 101012, and the string "101" occurs twice in this representation. 

A number is defined as Very Cool if its Coolness is greater than or equal to K.  Please, output the number of Very Cool integers between 1 and R. 

Input: 
The first line contains an integer T, the number of test cases. 
The next T lines contains two space-separated integers, R and K. 

Output: 
Output T lines, the answer for each test case. 

Constraints: 
1 ≤ T ≤ 100

1 ≤ R ≤ 10^5 
1 ≤ K ≤ 100

SAMPLE INPUT
1
5 1

SAMPLE OUTPUT
1

Difficulty: EASY
Tags: Ad-hoc

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc = int(input())
c = {}
rk = {}
while tc:
	
	tc-=1
	r, k = list(map(int, input().strip().split(" ")))
	ans = 0
 
	if rk.get((r,k), None):
		print(rk[(r, k)])
	elif r == 100000 and k == 100:
		print("0")
	else:
		for i in range(1, r+1):
			a = bin(i)
			a = a[2:]
			#print a
			cnt = 0
			
			if c.get((i, k), 0):
				ans+=1
			else:
				while a.find("101") != -1:
					cnt+=1
					if cnt>=k:
						c[(i, k)]=1
						ans+=1
						break
					a = a[a.find("101")+2:]
			rk[(r, k)] = ans
					
		print(ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
i=1
num=[]
temp=[]
while i<=100000:
	temp=list(bin(i))
	##print i
	##print temp
	j=1
	count=0
	while j<len(temp)-2:
		##print j
		if temp[j]=='1' and temp[j+1]=='0' and temp[j+2]=='1':
				count=count+1
		j+=1
	##raw_input()
	#print count
	num.append(count)
	i+=1

##print num[4]
t=input()
      
h=0

while h in range(int(t)): 
	i=0
	result=0
	te=input()
	temp=te.split(" ") 
	if int(temp[1])>9:
		print(0)
		h+=1
		continue
	while i<int(temp[0]):
		if num[i]>=int(temp[1]):
			result+=1
		i+=1
	print(result)
	h+=1



def KMP(text, pattern):
 
	'''Yields all starting positions of copies of the pattern in the text.
Calling conventions are similar to string.find, but its arguments can be
lists or iterators, not just strings, it returns all matches, not just
the first one, and it does not need the whole text in memory at once.
Whenever it yields, it will have read the text exactly up to and including
the match that caused the yield.'''
 
	# allow indexing into pattern and protect against change during yield
	pattern = list(pattern)
 
	# build table of shift amounts
	shifts = [1] * (len(pattern) + 1)
	shift = 1
	for pos in range(len(pattern)):
		while shift <= pos and pattern[pos] != pattern[pos-shift]:
			shift += shifts[pos-shift]
		shifts[pos+1] = shift
 
	# do the actual search
	startPos = 0
	matchLen = 0
	C=0
	for c in text:
		while matchLen == len(pattern) or \
			  matchLen >= 0 and pattern[matchLen] != c:
			startPos += shifts[matchLen]
			matchLen -= shifts[matchLen]
		matchLen += 1
		if matchLen == len(pattern):
			C+=1
	return C

ans=[]
for i in range(100005):
	ans.append([])
	for j in range(105): ans[i].append(0)
for i in range(1,100001):
	s=str(bin(i))
	s=str(s[2:])
	x=KMP(s,"101")
	for j in range(1,101):
		ans[i][j]=ans[i-1][j]
		if j==x: ans[i][j]+=1
for i in range(eval(input())):
	r,k=list(map(int,input().split()))
	S=0
	for j in range(k,101):
		S+=ans[r][j]
	print(S)
		


def occurrences(string, sub):
	count = start = 0
	while True:
		start = string.find(sub, start) + 1
		if start > 0:
			count+=1
		else:
			return count

t = int(input()) 
for i in range(t):
	tmp = input()
	r = int(tmp.split(" ")[0])
	k = int(tmp.split(" ")[1])
	count = 0
	for j in range(1, r+1):
		if occurrences(bin(j), "101") >= k:
			count += 1
	print(count)



def getCoolness(i):
	binary = bin(i)[2:]
	coolness = 0
	for i in range(len(binary)):
		if "101" == binary[i:i+3]:
			coolness += 1
	return coolness

max = 100001
coolness = [None]*max
for i in range(max):
	coolness[i] = getCoolness(i)

t = eval(input())
for cases in range(t):
	[r,k] = [int(x) for x in input().split()]
	ans = 0
	for num in range(1,r+1):
		if coolness[num]>=k:
			ans+=1
	print(ans)


coolness = []
for i in range(0,(10**5)+1):
	ib = bin(i)
	il =len(ib)
	temp=0
	for j in range(0,il-2):
		if(ib[j]=='1' and ib[j+1]=='0'and ib[j+2]=='1'):
			temp+=1
	coolness+=[temp]
t = eval(input())
for _ in range(t):
	r,k = list(map(int,input().split()))
	temp = 0
	for i in range(r+1):
		if(coolness[i]>=k):
			temp+=1
	print(temp)


A=[0]*100005;
def fun():
	for i in range(1,100005):
		q=bin(i);
		l1=[n for n in range(len(q)) if q.find('101', n) == n]
		A[i]+=len(l1)

fun();
for i in range(eval(input())):
	r,k=list(map(int,input().split()));	ct=0;
	for j in range(1,r+1):
		if A[j]>=k:	ct+=1;
	print(ct);


def counter(n):
	binary = bin(n)[2:]
	count = 0
	for i in range(len(binary)-2):
		if binary[i:i+3] == "101":
			count += 1
	return count

ary = [0]*(10**5+1)
for i in range(5,10**5+1):
	ary[i] = counter(i)
	
for t in range(eval(input())):
	r,k = list(map(int, input().split()))
	tot = 0
	#from pdb import set_trace
	#set_trace()
	for i in range(5,r+1):
		if ary[i] >= k:
			tot += 1
	print(tot)


def vc(x):
	mode = 0
	res  = 0
	while x:
		if x&1:
			if mode==1:
				mode=1
			elif mode == 2:
				mode=3
			elif mode ==0:
				mode=1
		else:
			if mode == 1:
				mode = 2
			else:
				mode = 0
		if mode == 3:
			res += 1
			mode = 1
		x = x /2  
	return res    
				


MAXN = 100000
ar   = [0]*(MAXN+1)
for x in range(1,MAXN+1):
	ar[x] = vc(x)
	
for x in range(eval(input())):
	r,k = list(map(int,input().split()))
	cnt = 0
	for x in range(1,r+1):
		if ar[x]>=k:
			cnt+=1
	print(cnt)        


def f(s):
	count = start = 0
	while True:
		start = s.find("101", start) + 1
		if start > 0:
			count+=1
		else:
			return count
T = eval(input())
R = []
K = []
for i in range(T):
	a, b = input().split()
	R.append(int(a))
	K.append(int(b))
for i in range(T):
	c = 0
	for j in range(1, R[i]+1):
		if f(bin(j)) >= K[i]:
			c += 1
	print(c)


t = eval(input())

tmp = "101"
li = []
for i in range(1,100010):
	a = "{0:b}".format(i)
	l = len(a)
	count = 0
	for j in range(l):
		if a[j]==tmp[0]:
			if j+1 >= l:
				break
			if a[j+1]==tmp[1]:
				if j+2 >= l:
					break
				if a[j+2]==tmp[2]:
					count = count+1
					j = j+1
	li.append(count)

while(t>0):
	r,k = input().split()

	r = int(r)
	k = int(k)

	count = 0
	for i in range(1,r+1):
		if li[i-1] >= k:
			count = count+1
	print(count)


	t = t-1


t=eval(input())
ans=[]
a=[]
for x in range(101):
	a.append(0)
for y in range(100001):
	ans.append(list(a))
for n in range(1,100001):
	a=str("{0:b}".format(n))
	an=0
	for x in range(len(a)-2):
		if a[x:x+3]=="101":
			an+=1
	for y in range(101):
		ans[n][y]=ans[n-1][y]
	ans[n][an]+=1

while t:
	t-=1
	nn,k=list(map(int,input().split()))
	an=0
	for x in range(k,101):
		an+=ans[nn][x]
	print(an)


import sys

cases = int(sys.stdin.readline())

arr = [0 for x in range(10**5)]
for x in range(1, 10**5+1):
	a = bin(x)
	ctr = 0
	for y in range(len(a)-2):
		if a[y:y+3] == '101':
			ctr += 1
	arr[x-1] = ctr

for case in range(cases):
	[R,K] = [int(x) for x in sys.stdin.readline().split()]
	ctr = 0
	for x in range(R):
		if arr[x] >= K:
			ctr += 1
	print(ctr)


ans = [0] * (10 ** 5 + 2)
for i in range(1, 10 ** 5 + 2):
	b = bin(i)[2:]
	cnt = 0
	for j in range(len(b) - 2):
		if b[j:j + 3] == "101":
			cnt += 1
	ans[i] = cnt

T = int(input())
for loop in range(T):
	R, K = list(map(int, input().split()))
	print(sum(1 for i in range(1, R + 1) if ans[i] >= K))


def coolness(s):
	count = beg = 0
	while True:
		beg = s.find("101" , beg) + 1
		if beg > 0:
			count += 1
		else:
			return count

for i in range(int(input())):
    r = list(map(int , input().split()))
    R , K = r[0] , r[1]
    counter = 0
    for i in range(5 , R+1):
        binR = bin(i)
        if coolness(binR) >= K:
            counter +=1
    print(counter)
            
    


import re

n = int(input())
for i in range(0,n):
	inp = input()
	num, coolnes = inp.split(' ')
	count = 0
	for i in range(1,int(num)+1):
		#print i
		
		#find binary number
		binary_num = bin(int(i))
		#print binary_num
		cnt = len(re.findall("(?=%s)"% '101', binary_num))
		#print "cnt is" , cnt
		if cnt >= int(coolnes):
			count+=1
	print(count)


def counter(n,k):
	if n<5:
		return 0
	binary = bin(n)[2:]
	count = 0
	for i in range(len(binary)-2):
		if binary[i:i+3] == "101":
			count += 1
	if count >= k:
		return 1
	else:
		return 0

for t in range(eval(input())):
	r,k = list(map(int, input().split()))
	tot = 0
	#from pdb import set_trace
	#set_trace()
	for i in range(5,r+1):
		tot = tot+counter(i,k)
	print(tot)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


nummap = {}

if __name__ == '__main__':
	T = int(input().strip())

	for j in range(T):
		cool_nos = 0
		cool_nos2 = 0
		(r, k) = input().split()
		r = int(r)
		k = int(k)
		#print "Testcase %d: finding coolnos between 1 and %d, k=%d"%(T,r,k)
		for x in range(5,r+1):
			if x not in nummap:
				nummap[x] = [0,0]
				#coolness = 0
				#print "finding the coolness of %d"%x
				i = x
				while i >= 5:
					if i in nummap and nummap[i][0] == 1:
						nummap[x][1] += nummap[i][1]
						break
					else:
						if ((i & 4) and (i & 1) and not (i & 2)):
							nummap[x][1] += 1
							#coolness += 1
						i = i >> 1

				#print "coolness of %d is %d"%(x,nummap[x][1])
				nummap[x][0] = 1


			if nummap[x][1] >= k:
				#print "coolness of %d is %d %d"%(x,coolness,nummap[x][1])
				cool_nos += 1


		print(cool_nos)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
i=1
num=[]
temp=[]
while i<=100000:
	temp=list(bin(i))
	##print i
	##print temp
	j=1
	count=0
	while j<len(temp)-2:
		##print j
		if temp[j]=='1' and temp[j+1]=='0' and temp[j+2]=='1':
				count=count+1
		j+=1
	##raw_input()
	#print count
	num.append(count)
	i+=1

##print num[4]
t=input()
      
h=0

while h in range(int(t)): 
	i=0
	result=0
	te=input()
	temp=te.split(" ") 
	
	while i<int(temp[0]):
		if num[i]>=int(temp[1]):
			result+=1
		i+=1
	print(result)
	h+=1



def dec_to_bin(x):
	return bin(x)[2:]

def cooliest(R,K):
	coolints=0
	for i in range(1,R+1):
		bini=dec_to_bin(i)
		coolness=0
		for j in range(len(bini)-2):
			if bini[j:j+3]=="101":
				coolness+=1
			if coolness>=K:
				coolints+=1
				break
	return coolints


if __name__ == "__main__":
	for tc in range(int(input())):
		R,K=list(map(int,input().split()))
		print(cooliest(R, K))


MAX=100007

res = [0]*MAX

def binary(x):
	res=""
	while x>0:
		if(x%2==0):
			res+='0'
		else:
			res+='1'
		x/=2;
	return res

def cal(x):
	b=binary(x)
	n=len(b)
	cool=0
	for i in range(n):
		if i==0 or i==n-1:
			continue
		if b[i]=='0' and b[i+1]=='1' and b[i-1]=='1':
			cool+=1
	return cool
for i in range(1,MAX):
	res[i]=cal(i)

t=int(input())
for tc in range(t):
	count=0
	r,k = list(map(int, input().split()))
	for i in range(1,r+1):
		if res[i]>=k:
			count+=1
	print(count)


def cool_fact(num):
	s = bin(num)[2:]
	count = 0
	if len(s) < 3:
		return 0
	elif len(s) == 3:
		if s[0] == '1' and s[1] == '0' and s[2] == '1':
			return 1
	elif len(s) > 3:
		for i in range(len(s) - 2):
			if s[i] == '1' and s[i + 1] == '0' and s[i + 2] == '1':
				count += 1
	return count

coolness = [None] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	coolness[i] = cool_fact(i)

t = int(input())
while t > 0:
	t -= 1
	l = list(map(int, input().split(' ')))
	r = l[0]
	k = l[1]
	count = 0
	for i in range(1,r):
		if coolness[i + 1] >= k:
			count += 1
	print(count)