402820: GYM100889 D Dicy Numbers

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 M^th prime number. For example, as 3^rd 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 10⁹ + 7.

The first line contains T(1 ≤ T ≤ 5 * 10⁵), the number of test cases. Each test case contains two numbers N and M(1 ≤ N ≤ 2 * 10⁶ and 1 ≤ M ≤ 10⁹).

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

2
2 3
4 5

3
15

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.