Description

Recently, Mingming has become obsessed with a certain kind of necklace. It is basically the same as other pearl necklaces, but its beads are special: they are carved from Taishan stone into regular triangular prisms.

The prism has three square lateral faces, and each face is engraved with a number. A necklace that satisfies Mingming must meet the following conditions:

1. The necklace consists of $n$ beads.
2. On each bead, every number $x$ must satisfy $0 < x \le a$, and the greatest common divisor of the three numbers on the bead must be exactly $1$.
3. Adjacent beads must be different. Two beads are considered the same if and only if they can be made identical by rotation or reflection.
4. Two necklaces are considered the same if they can become identical after a rotation.

Mingming is curious: given $n$ and $a$, how many different necklaces are there? Since the answer can be large, output it modulo $10^{9}+7$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.
Then follow $T$ lines, each containing two integers $n$ and $a$.

Output Format

For each test case, output one integer, the number of different necklaces.

1
2  2

3

Hint

There are three kinds of beads that meet the conditions: [1,1,1], [1,1,2], [1,2,2].

The valid sequences they can form are: [1,2], [1,3], [2,3].

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 10$, $2 \le n \le 10^{14}$, $1 \le a \le 10^7$.

Translated by ChatGPT 5