Going for Relief
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…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.
Inputs start with Testcase T For each case, there will be two number N number of the house in the flood-affected area and C the cost.
1 ≤ T ≤ 105
1 ≤ N ≤ 106
1 ≤ C ≤ 1018
For each case print the number of such paths. as the result can be very big you have to print answer % (109 + 7).
3 4 2 3 2 2 2
18 12 2