题目描述

给定一个正整数 $n$ 和一个不小于 $5$ 的素数 $p$。

寻找满足以下条件的整数三元组 $(x,y,z)$。

• $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$ 个测试用例。

约束条件

• $1\leq T\leq 10^5$
• $1\leq n\leq 10^9$
• $p$ 是一个满足 $5\leq p\leq 10^9$ 的素数。

输入

从标准输入读入数据，格式如下：

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

每个测试用例的格式如下：

$n$ $p$

输出

输出 $T$ 行。第 $i$ 行应包含用空格分隔的 $x,y,z$ 值，其中 $(x,y,z)$ 是第 $i$ 个测试用例的解之一。

如果存在多个解，你可以输出任意一个。

示例一

3
1 7
2 7
10 998244353

示例一输出

1 4 6
1 2 5
20380119 21549656 279594297

对于第一个测试用例：

• $(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}$，所以满足条件。