Key to C


Given two numbers, n and p, you need to find out all the subsets of n, which differ at atmost p positions from their reverse in binary representation.
Subset of n - Consider the binary representation of number n. Now you can change this binary representation by unsetting the set bits. All the possible combinations which can be obtained by changing '1' bits to '0' bits in the binary representation of n are included in its subset. For example,
Let n = 13 (1101), then subset(13) = {"1100","1000","0100","0000","1101","1001","0101","0001"}. or subset(13) = {12,8,4,0,13,9,5,1}.
Added Clarification : You need to reverse all the 32-bits. We thought it was implicit from the statement.

Input Specification

The first line of the input contains T,the number of test cases. Then, T lines follow, each containing two non-negative numbers, n and p.

Output Specification

For each test case, in first line print the number of valid subsets, N.

Sample Input

2
4 1
9 10

Sample Output

1
4

Constraints

0 <= n <= 2^20.
0 <= p <= 100.
There are no "#define" allowed in the code.
Time limit: 7s   Memory Limit: 32MB

Scoring

c = number of non-whitespace characters - number of semi-colons
w = number of whitespaces
k = number of C keywords
s = number of semi-colons
S = k*50 + s*10 + w*5 + c;
You have to minimize S. The scoring will be relative to S.