Iterated Bitcount Function

Problem code: IBT

All submissions for this problem are available. 

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 separated 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.

Example

Input
6
1 1
2 1
3 1
3 2
13 3
20 2

Output
1
2
2
1
3
10


Constraints
  • 1 <= T <= 1000
  • 1 <= N <= 10^500
  • 1 <= K <= 10
    Date: 2010-09-28
    Time limit: 3s
    Source limit: 50000
    Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2


    Comments

    admin: The submission by

    Shubham28 @ 1 Oct 2010 10:48 PM

    admin: The submission by Varun Jalan is for Testing purpose. His solution would not be considered for Ranking.

    SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

    CodeChef is a global programming communityCodeChef hosts online programming competitions