ITERBIT - Iterated Bitcount Function

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.

Sample

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


Added by:Varun Jalan
Date:2010-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC VB.NET
Resource:own problem, used for Al Khwarizm '10

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.