# 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

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 ≤ 10 ^{5}**

**1 ≤ N ≤ 10 ^{6}**

**1 ≤ C ≤ 10 ^{18}**

## Output

For each case print the number of such paths. as the result can be very big you have to print **answer % (10 ^{9} + 7)**.

## Samples

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

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

Login to submit