cool_number

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

1 ≤ K ≤ 100

SAMPLE INPUT
1
5 1

SAMPLE OUTPUT
1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
for _ in range(eval(input())):
	a,k=list(map(int,input().split()))
	lst=[]
	
	
	while a>0:
		j=str(bin(a)[2:])
		#print j
		d=len(j)
		p,count=0,0
		while p<d:
			if d<3:
				break
			else:
				if d-p>2:
					if (((j[p]=='1') and j[p+1]=='0') and j[p+2]=='1'):
						count = count+1
						p=p+1
					else:
						p=p+1
				else:
					break
		lst.append(count)
		a=a-1
	
	#print lst
	flag=0
	for it in lst:
		if it>=k:
			flag=flag+1
	print(flag)
		


def coolness(n):
	c=0
	b=bin(n)
	for i in range(2,len(b)-2):
		if b[i:i+3:]=='101':
			c+=1
	return c
 
d=[0]*((10**5)+1)
for x in range(1,10**5+1):
	d[x]=coolness(x) 
for t in range(int(input())):
	r,k=list(map(int,input().split()))
	ans=0
	for coolints in range(1,r+1):
		if d[coolints]>=k:
			ans+=1
	print(ans)  


from sys import stdin

counter = [0]*100001
for r in range(1, 100001):
	last = 0
	s = bin(r)
	while s.find('101', last) != -1:
		last = s.find('101', last) + 1
		counter[r] += 1

nextint = iter(map(int, stdin.read().split())).__next__
for x in range(nextint()):
	r, k = nextint(), nextint()
	print(len([x for x in range(1, r + 1) if counter[x] >= k]))



def occurrences(string, sub):
	count = start = 0
	while True:
		start = string.find(sub, start) + 1
		if start > 0:
			count+=1
		else:
			return count
			
def cool():
	for _ in range(eval(input())):
		count = 0
		R, K = list(map(int, input().split()))
		for i in range(1, R+1):
			bin = str('{0:08b}'.format(i))
			
			if occurrences(bin, '101') >= K:
				count += 1
		
		print(count)


if __name__ == "__main__":
	cool()