# 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
```

### Statistics

56% Solution Ratio

kzvd4729Earliest, 6M ago

jisan047Fastest, 0.4s

Tarik.amtolyLightest, 5.1 MB

chayankumar999Shortest, 1614B