Color

Beads of n colors are connected together into a circular necklace of n beads (n ≤ 10^9). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the n colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected.

You only need to output the answer module a given number p.

Input

The first line contains the number of test cases x (x ≤ 3500). Each of the following x lines contains two numbers n and p (1 ≤ n ≤ 10^9, 1 ≤ p ≤ 30000), representing a test case.

Output

For each test case, output one line containing the answer.

Examples