P3307 [SDOI2013] Necklace

As one of the body ornaments, the necklace is among the earliest pieces of jewelry. Besides its decorative function, some necklaces also have special symbolic roles, such as the crucifix chain for Catholics and the prayer beads for Buddhists. From ancient times to the present, people have created necklaces of various styles, features, and forms to beautify the human body and the environment, meeting the aesthetic needs of people with different skin tones, ethnicities, and tastes. In terms of materials, necklaces on the jewelry market include gold, silver, gemstones, and more. A pearl necklace is an ornament made of pearls, which are pierced and strung together to be worn around the neck. Natural pearl necklaces are believed to have certain protective qualities.

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$.

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$.

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

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