Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Going for Relief

By jisan047 · Limits 1s, 512 MB

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

InputOutput
3
4 2
3 2
2 2
18
12
2

Discussion

Statistics


56% Solution Ratio

kzvd4729Earliest, 6M ago

jisan047Fastest, 0.4s

Tarik.amtolyLightest, 5.1 MB

chayankumar999Shortest, 1614B

Submit

Login to submit

Related Contests

#HelpFloodVictims Programming Contest 2019 Ended at 2019-08-23 16:00:00 +0000 UTC