Description

Beads of N colors are connected together into a circular necklace of N beads (N<=1000000000). Your j ob is to calculate how many different kinds of the necklace can be produced. You should know that th e necklace might not use up all the N colors, and the repetitions that are produced by rotation arou nd the center of the circular necklace are all neglected.You only need to output the answer module a given number P.

现在有N种颜色的珠子，我们要做一个N个珠子组成的环形项链（N≤1000000000）。 你的任务是计算可以生产多少种不同的项链。注意项链并不一定要用到所有颜色的珠子， 而且旋转之后等同的项链被认为是一样的。 只需要输出这个总数Mod P的余数。

Format

Input

The first line of the input is an integer X (X <= 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 <= N <= 1000000000, 1 <= P <= 30000), representing a test case.

Output

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

Samples

5
1 30000
2 30000
3 30000
4 30000
5 30000

1
3
11
70
629