Thanos is changed. He helps the helpless. He recently makes a plan to go for relief to the flood-affected people.
In the flood-affected area, there are N house numbered from 1 to N.
Thanos can directly move one house to another if the number of both houses is prime or both are composite or one of the two houses is numbered 1 with cost 1 unit, for example, 2 ➝ 3, 3 ➝ 2, 4 ➝ 8, 8 ➝ 4, 1 ➝ 2, 2 ➝ 1, 1 ➝ 4, 4 ➝ 1 is valid move but 2 ➝ 4 is not valid. You are Ebony Maw, Thanos asks you how many paths are there which costs exactly C units.
Input
The input starts with the number of test cases T (1 ≤ T ≤ 105).
For each case, there will be two numbers N (1 ≤ N ≤ 106), the number of the house in the flood-affected area, and C (1 ≤ C ≤ 1018), the cost.
Output
For each case print the number of such paths. As the result can be very large you have to print the answer mod 109 + 7.
Sample
| Input | Output |
|---|---|
3 4 2 3 2 2 2 | 18 12 2 |
