Problem Statement
You are given a positive integer n, and a prime number p at least 5.
Find a triple of integers (x,y,z) that satisfies all of the following conditions.
- 1leqx<y<zleqp−1.
- (x+y+z)(xn+yn+zn)(x2n+y2n+z2n)equivx3n+y3n+z3npmodp.
It can be proved that such a triple (x,y,z) always exists.
You have T test cases to solve.
Constraints
- 1leqTleq105
- 1leqnleq109
- p is a prime number satisfying 5leqpleq109.
The input is given from Standard Input in the following format:
T
textcase1
vdots
textcaseT
Each case is in the following format:
n p
Output
Print T lines. The i-th line should contain x,y,z with spaces in between where (x,y,z) is a solution for the i-th test case.
If multiple solutions exist, you may print any of them.
Sample Output 1
For the first test case:
- (x+y+z)(xn+yn+zn)(x2n+y2n+z2n)=(1+4+6)(1+4+6)(1+16+36)=6413, and
- x3n+y3n+z3n=1+64+216=281.
We have 6413equiv281pmod7, so the conditions are satisfied.