CF2147G.Modular Tetration

For a positive integer $a$, we define a recurrence ${b_n}_{n\geq 0}$ as $b_n = a^{b_{n-1}}$, with $b_0 = 1$.

We say that a positive integer $a$ is $m$-tetrative if the sequence $b$ stabilizes to $1$ modulo $m$, that is, there exists $N \ge 0$ such that $b_n \equiv 1 \pmod m$ for all $n \geq N$.

For a given $m$, calculate the density of the $m$-tetrative integers. Here, the density of a set $S$ is the limit $$\lim\limits_{n\rightarrow \infty}\frac{|S\cap [1,2,\ldots,n]|}{n}.$$ Informally, it is the "proportion" of positive integers that are $m$-tetrative.

It can be proven (under the constraints of this problem) that the density is well-defined and is always a rational number, whose denominator is not divisible by $998\,244\,353$.

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

若正整数 $a$ 满足：序列 $b$ 在模 $m$ 意义下稳定于 $1$，即存在 $N \ge 0$，使得对所有 $n \geq N$ 均有 $b_n \equiv 1 \pmod m$，则称 $a$ 是 $m$-四次幂型的（$m$-tetrative）。

对给定的 $m$，计算所有 $m$-四次幂型正整数的密度。此处，集合 $S$ 的密度定义为极限

$$\lim\limits_{n\rightarrow \infty}\frac{|S\cap [1,2,\ldots,n]|}{n}.$$

直观上，它表示正整数中 $m$-四次幂型整数所占的“比例”。

可以证明（在本题约束条件下），该密度恒存在，且总是一个有理数，其分母不被 $998\,244\,353$ 整除。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The number $m$ will be given to you as a product of three integers $x$, $y$, and $z$. The first and only line of each test case contains three integers $x$, $y$, $z$ ($1\leq x,y,z \leq 10^6$, $m = xyz \geq 2$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）。

For each test case, print the density of $m$-tetrative integers ($a$ such that its corresponding sequence $b_n$ converges to $1$ modulo $m$), modulo $998\,244\,353$.

Formally, let $M = 998\,244\,353$. It can be shown that the exact answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对于每个测试用例，输出 $m$-四重幂整数（即满足其对应序列 $b_n$ 模 $m$ 收敛于 $1$ 的整数 $a$）的密度，对 $998\,244\,353$ 取模。

形式化地，令 $M = 998\,244\,353$。可以证明，精确答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first test case, $m = 5$. For example, $a=1$ is $5$-tetrative since $b_n = 1$ for all $n$. For $a= 8$, the sequence $b$ is $[1, 8, 8^8, 8^{(8^8)}, \ldots]$, which is $[1, 3, 1, 1, \ldots]$ if we look at it modulo $5$. It can be proven that the sequence is always $1 \pmod 5$ for big enough $n$, so $8$ is $5$-tetrative. For $a=10$, the sequence $b$ is $[1, 10, 10^{10}, 10^{(10^{10})}, \ldots]$, which is $[1, 0, 0, 0, \ldots]$ if we look at it modulo $5$. It can be proven that the sequence is always $0 \pmod 5$ for big enough $n$, so $10$ is not $5$-tetrative. The answer for the first test case is $\frac{1}{2}$.

In the second test case, $m= 10$ and the answer is $\frac{1}{10}$.

In the third test case, $m= 23$ and the answer is $\frac{63}{506}$.

In the fourth test case, $m= 200$ and the answer is $\frac{1}{200}$.

In the fifth test case, $m= 999$ and the answer is $\frac{1}{222}$.

在第一个测试用例中，$m = 5$。例如，$a=1$ 是 $5$-四叠数（$5$-tetrative），因为对所有 $n$ 均有 $b_n = 1$。对于 $a= 8$，序列 $b$ 为 $[1, 8, 8^8, 8^{(8^8)}, \ldots]$，若对其模 $5$ 观察，则变为 $[1, 3, 1, 1, \ldots]$。可以证明：当 $n$ 足够大时，该序列恒满足 $b_n \equiv 1 \pmod{5}$，因此 $8$ 是 $5$-四叠数。对于 $a=10$，序列 $b$ 为 $[1, 10, 10^{10}, 10^{(10^{10})}, \ldots]$，若对其模 $5$ 观察，则变为 $[1, 0, 0, 0, \ldots]$。可以证明：当 $n$ 足够大时，该序列恒满足 $b_n \equiv 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}$。