511. Fermat's Last Theorem
Time limit per test: 0.75
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Given a positive integer
n and a positive prime number
p, find
x,
y and
z such that
x^{n}+
y^{n}=z
^{n} modulo
p and
x,
y and
z are nonzero modulo
p or report that there's no such triple.
Input
The first line of the input file contains the number
t of testcases to solve, 1 ≤
t ≤ 1000. Each of the next
t lines contains two integers
n and
p, 3 ≤
n ≤ 10
^{6}, 2 ≤
p ≤ 10
^{6}.
Output
For each input testcase, output one line:
 when there exists a solution, output three integers x, y and z, 1 ≤ x, y, z ≤ p1. If there are multiple solutions, output any.
 when there's no solution, output one integer 1.
Example(s)
sample input

sample output

2
5 41
3 5

1
1 2 4
