SP7356 ITERBIT - Iterated Bitcount Function
Description
Let f(x) be the number of 1's in the binary representation of x.
We can define f^k(x) as f(x) for k = 1, and f^(k-1)(f(x)) for k > 1.
Let f^\*(x) be the smallest k >= 1 such that f^k(x) = 1.
Given N and K, how many numbers x between 1 and N inclusive have f^\*(x) = K ?
Input :
The first line contains the number of test cases T. Each of the next T lines contains two space seperated numbers N and K.
Output :
Output one line corresponding to each test case, containing the answer for the corresponding test case. Output all answers modulo 1000000007.
Sample Input :
6
1 1
2 1
3 1
3 2
13 3
20 2
Sample Output :
1
2
2
1
3
10
Constraints :
1
Input Format
N/A
Output Format
N/A