CFCF2147G.Modular Tetration

对于一个正整数 $a$，我们定义递推数列 $\{b_n\}_{n\geq 0}$ 为 $b_n = a^{b_{n-1}}$，其中 $b_0 = 1$。

我们说一个正整数 $a$ 是 $m$-四重幂的，如果数列 $b$ 从某一项开始在模 $m$ 的意义下稳定为 $1$，即存在 $N \ge 0$，使得对于所有 $n \geq N$，都有 $b_n \equiv 1 \pmod m$。

给定 $m$，计算 $m$-四重幂整数的密度。其中，集合 $S$ 的密度定义为

$$\lim_{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$ 的乘积 $m = xyz$ 给出。每组仅一行，包含三个整数 $x、y、z$，满足 $1\leq x,y,z \leq 10^6$，且 $m = xyz \geq 2$。

对于每个测试用例，输出 $m$-四重幂整数的密度（即所有满足条件的 $a$ 的密度模 $998\,244\,353$）。

具体来说，设 $M=998\,244\,353$，可证明答案可表示为最简分数 $\frac{p}{q}$，其中 $p$、$q$ 均为整数，且 $q \not\equiv 0 \pmod M$。请输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$ 的唯一整数 $x$。

在第一个样例中，$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]$，最终稳定为 $1$，因此 $8$ 也是 $5$-四重幂的。而 $a=10$ 时，数列 $b$ 为 $[1,10,10^{10},10^{(10^{10})},\ldots]$，模 $5$ 后为 $[1,0,0,0,\ldots]$，最终稳定为 $0$，不是 $5$-四重幂的。第一个样例的答案为 $\frac{1}{2}$。

第二个样例，$m=10$，答案为 $\frac{1}{10}$。

第三个样例，$m=23$，答案为 $\frac{63}{506}$。

第四个样例，$m=200$，答案为 $\frac{1}{200}$。

第五个样例，$m=999$，答案为 $\frac{1}{222}$。