402820: GYM100889 D Dicy Numbers

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Dicy Numberstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

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

加入题单

上一题 下一题 算法标签: