#P17016. [SGU511] Fermat's Last Theorem

[SGU511] Fermat's Last Theorem

[SGU511] Fermat's Last Theorem

题目描述

给定正整数 nn 和素数 pp,请找出三个模 pp 非零的整数 x,y,zx,y,z,使得

xn+yn≡zn(modp)x^n+y^n\equiv z^n\pmod p。

也就是说,需要满足 1≤x,y,z≤p−11\le x,y,z\le p-1。如果不存在这样的三元组,则输出 -1。

每个测试点包含多组询问,各组询问相互独立。

输入格式

第一行包含一个整数 tt,表示询问组数,1≤t≤10001\le t\le1000。

接下来 tt 行,每行包含两个整数 n,pn,p,满足 3≤n≤1063\le n\le10^6,2≤p≤1062\le p\le10^6,并保证 pp 为素数。

输出格式

对于每组询问输出一行:

  • 若存在解,输出三个整数 x,y,zx,y,z,满足 1≤x,y,z≤p−11\le x,y,z\le p-1 且 xn+yn≡zn(modp)x^n+y^n\equiv z^n\pmod p;若有多组解,输出任意一组即可;
  • 若不存在解,输出一个整数 -1。

样例

样例输入

2
5 41
3 5

样例输出

-1
1 2 4

注意:对于有解的询问,样例输出并不是唯一答案。