Necklaces are one of the oldest forms of human adornment. Beyond their decorative function, some necklaces serve special purposes, such as the crucifix chains worn by Catholics or the prayer beads used by Buddhists. Throughout history, people have created necklaces of various styles, characteristics, and designs to beautify themselves and their environment, catering to the aesthetic needs of people of different skin tones, ethnicities, and tastes. In terms of materials, necklaces on the jewelry market are typically made of gold, silver, or gemstones. Pearl necklaces are ornaments made of pearls, created by drilling holes in pearls and stringing them together to be worn around the neck. Natural pearl necklaces are also believed to have certain health-preserving properties.

Recently, Mingming has become obsessed with a particular type of necklace. While similar to other pearl necklaces, the beads of this necklace are unique: they are carved from Taishan stone in the shape of regular triangular prisms, with numbers engraved on their sides. A necklace that satisfies Mingming must meet the following conditions:

1. The necklace consists of $n$ beads.
2. The number $x$ on each bead must satisfy $0 < x \leq a$, and the greatest common divisor of the numbers on all beads must be exactly $1$. Two beads are considered identical if and only if one can be transformed into the other by rotation or flipping.
3. Adjacent beads must be different.
4. Two necklaces are considered identical if one can be transformed into the other by rotation.

Mingming is curious about how many different necklaces can be formed given $n$ and $a$. Since the answer may be very large, output the result modulo $1\,000\,000\,007$.

Input

The input consists of multiple test cases.

The first line contains an integer $T \leq 10$, representing the number of test cases.

Each of the following $T$ lines contains two integers $n$ and $a$.

Output

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

Examples

Input 1

1
2 2

Output 1

3

Subtasks

For $20\%$ of the data, $T = 1$.

An additional $10\%$ of the data has $n \leq 10, a \leq 10$.

An additional $10\%$ of the data has $n \leq 10^3, a \leq 100$.

An additional $20\%$ of the data has $n \leq 10^6, a \leq 10^5$.

An additional $20\%$ of the data has $n \leq 10^9, a \leq 100$.

An additional $10\%$ of the data has $n \leq 10^9, a \leq 10^5$.

For $100\%$ of the data: $1 \leq n \leq 10^{14}, 1 \leq a \leq 10^7, 1 \leq T \leq 10$.