题目描述

正整数 $n$ および，$5$ 以上の素数 $p$ が与えられます．

次の条件をすべて満たす整数の組 $(x,y,z)$ を 1 つ求めてください．

• $1\leq\ x\ <\ y\ <\ z\ \leq\ p\ -\ 1$.
• $ (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n})\ \equiv\ x^{3n}+y^{3n}+z^{3n}\pmod{p} $.

なお，このような組 $(x,y,z)$ は必ず存在することが証明できます．

$T$ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

输入格式

入力は以下の形式で標準入力から与えられます．

$T$ $\text{case}_1$ $\vdots$ $\text{case}_T$

各テストケースは以下の形式で与えられます．

$n$ $p$

输出格式

$T$ 行出力してください．$i$ 行目には $i$ 番目のテストケースの解を $(x,y,z)$ とするとき，$x,y,z$ をこの順に空白区切りで出力してください．

解が複数存在する場合，どれを出力しても正解となります．

题目大意

$T$ 组数据。每组数据给定一正整数 $n$ 和一不小于 $5$ 的素数 $p$。

试构造三元组 $(x,y,z)$ 满足：

• $1 \le x < y < z \le p - 1$

• $(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n} (\bmod \space p)$

能够证明解一定存在。

题目保证 $1 \le T \le {10}^5$，$1 \le n,p \le {10}^9$，$p$ 是素数。

3
1 7
2 7
10 998244353

1 4 6
1 2 5
20380119 21549656 279594297

提示

制約

• $1\leq\ T\leq\ 10^5$
• $1\leq\ n\leq\ 10^9$
• $p$ は $5\leq\ p\leq\ 10^9$ を満たす素数

Sample Explanation 1

ひとつめのテストケースについて， - $ (x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n})\ =\ (1+4+6)(1+4+6)(1+16+36)\ =\ 6413 $ - $ x^{3n}+y^{3n}+z^{3n}\ =\ 1\ +\ 64\ +\ 216\ =\ 281 $ であり，$6413\equiv\ 281\pmod{7}$ なので，条件を満たしていることが確認できます．