# Practice on Toph

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

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

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.

The input starts with the number of test cases **T** (1 ≤ T ≤ 10^{5}).

For each case, there will be two numbers **N** (1 ≤ N ≤ 10^{6}), the number of the house in the flood-affected area, and **C** (1 ≤ C ≤ 10^{18}), the cost.

For each case print the number of such paths. As the result can be very large you have to print the answer mod 10^{9} + 7.

Input | Output |
---|---|

3 4 2 3 2 2 2 | 18 12 2 |

56% Solution Ratio

kzvd4729Earliest,

jisan047Fastest, 0.4s

Tarik.amtolyLightest, 5.1 MB

chayankumar999Shortest, 1614B

Login to submit