Beads of \textbf{n} colors are connected together into a circular necklace of \textbf{n }beads (\textbf{n }≤ \textbf{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 \textbf{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 \textbf{p}. \InputFile The first line contains the number of test cases \textbf{x }(\textbf{x }≤ \textbf{3500}). Each of the following \textbf{x }lines contains two numbers \textbf{n }and \textbf{p }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^9}, \textbf{1 }≤ \textbf{p }≤ \textbf{30000}), representing a test case. \OutputFile For each test case, output one line containing the answer.