D. Dicy Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two positive integers N and M.

Let function denote the number of distinct positive divisors of k. For example, , .

The set is defined as the set of all positive integers i such that and all prime factors of i are less than or equal to the Mth prime number. For example, as 3rd prime number is 5 and the numbers with prime factors less than or equal to 5 with number of positive divisors  = 2 are 2, 3, 5.

You have to print the number of elements in . As this number can be very large, print this number modulo 109 + 7.

Input

The first line contains T(1 ≤ T ≤ 5 * 105), the number of test cases. Each test case contains two numbers N and M(1 ≤ N ≤ 2 * 106 and 1 ≤ M ≤ 109).

Output

Output for each test case the answer in a separate line.

Example
Input
2
2 3
4 5
Output
3
15
Note

Sample test case 1:

The 3rd prime number is .

Sample test case 2:

The 5th prime number is

As these are the only numbers with number of divisors equal to 4 and prime factors  ≤ 11.