G. 模四元化
每次测试时间限制：$2$ 秒
每次测试内存限制：$256$ 兆字节

---

对于正整数 $a$，我们递归定义序列 $\{b_n\}_{n \ge 0}$ 为

$$b_n = a^{b_{n-1}},$$

其中 $b_0 = 1$。

称正整数 $a$ 是 $m$-四元律（$m$-stable），如果序列 $b_n$ 模 $m$ 稳定到 $1$，即存在 $N \ge 0$ 使得对所有 $n \ge N$ 都有

$$b_n \equiv 1 \pmod m。$$

对于给定的 $m$，计算 $m$-四元律的密度。
集合 $S$ 的密度定义为

$$\lim_{n \to \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 \le x, y, z \le 10^6$，且 $m = xyz \ge 2$）。

---

输出
对于每个测试用例，输出 $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 < M$ 且 $x \cdot q \equiv p \pmod M$。

---

示例
输入：

5
5 1 1
5 2 1
23 1 1
10 10 2
9 3 37

输出：

499122177
299473306
893685162
913393583
705965601

---

注释

• 第一个测试用例中，$m = 5$。
  例如，$a = 1$ 是 $5$-四元律，因为 $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}$？注释中写的是 $110$ 但实际应是分数，输出模意义下的值。

• 第三个测试用例 $m = 23$，密度为 $\frac{6}{35}$？

• 第四个测试用例 $m = 200$，密度为 $\frac{1}{200}$？

• 第五个测试用例 $m = 999$，密度为 $\frac{12}{22}$？