对于正整数 $$$a$$$,我们将递归 $$$\{b_n\}_{n\geq 0}$$$ 定义为 $$$b_n = a^{b_{n-1}}$$$,其中 $$$b_0 = 1$$$。
我们说正整数 $$$a$$$ 是 $$$m$$$-四定 如果序列$$$b$$$稳定到$$$1$$$模$$$m$$$,也就是说,存在$$$N \ge 0$$$,使得$$$b_n \equiv 1 \pmod m$$$对于所有$$$n \geq N$$$。
对于给定的 $$$m$$$,计算 $$$m$$$- 的密度四定 整数。这里,集合 $$$S$$$ 的密度是极限 $$\lim\limits_{n\rightarrow \infty}\frac{|S\cap [1,2,\ldots,n]|}{n}。$$ 非正式地,它是 $$$m$$$- 的正整数的“比例”四定.
可以证明(在该问题的约束下)密度是明确定义的并且始终是一个有理数,其分母不能被 $$$998\,244\,353$$$ 整除。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
数字 $$$m$$$ 将作为三个整数 $$$x$$$、$$$y$$$ 和 $$$z$$$ 的乘积提供给您。每个测试用例的第一行也是唯一一行包含三个整数 $$$x$$$、$$$y$$$、$$$z$$$ ($$$1\leq x,y,z \leq 10^6$$$, $$$m = xyz \geq 2$$$)。
输出
对于每个测试用例,打印 $$$m$$$- 的密度四定 整数($$$a$$$,使得其对应的序列 $$$b_n$$$ 收敛到 $$$1$$$ 模 $$$m$$$),模 $$$998\,244\,353$$$。
正式地,令 $$$M = 998\,244\,353$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$ 使得 $$$0 \le x \lt M$$$ 和 $$$x \cdot q \equiv p \pmod{M}$$$ 。
示例
输入复制
55 1 15 2 123 1 110 10 29 3 37
输出复制
499122177299473306893685162913393583705965601
注意
在第一个测试用例中,$$$m = 5$$$。例如,$$$a=1$$$ 是 $$$5$$$-四定 因为对于所有 $$$n$$$,$$$b_n = 1$$$。对于 $$$a= 8$$$,序列 $$$b$$$ 是 $$$[1, 8, 8^8, 8^{(8^8)}, \ldots]$$$,如果我们看它对 $$$5$$$ 取模的话,它是 $$$[1, 3, 1, 1, \ldots]$$$。可以证明,对于足够大的 $$$n$$$,序列始终是 $$$1 \pmod 5$$$,因此 $$$8$$$ 是 $$$5$$$-四定。对于 $$$a=10$$$,序列 $$$b$$$ 是 $$$[1, 10, 10^{10}, 10^{(10^{10})}, \ldots]$$$,如果我们对 $$$5$$$ 取模,则为 $$$[1, 0, 0, 0, \ldots]$$$。可以证明,对于足够大的 $$$n$$$,序列始终是 $$$0 \pmod 5$$$,因此 $$$10$$$ 不是 $$$5$$$-四定。第一个测试用例的答案是 $$$\frac{1}{2}$$$。
在第二个测试用例中,$$$m= 10$$$,答案是$$$\frac{1}{10}$$$。
在第三个测试用例中,$$$m= 23$$$,答案是$$$\frac{63}{506}$$$。
在第四个测试用例中,$$$m= 200$$$,答案是$$$\frac{1}{200}$$$。
在第五个测试用例中,$$$m= 999$$$,答案是$$$\frac{1}{222}$$$。