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…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

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

Output

For each case print the number of such paths. as the result can be very big you have to print answer % (109 + 7).

Samples

InputOutput
3
4 2
3 2
2 2
18
12
2


Discussion