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$.

Input

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$).

Output

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}$.

Note

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}$.