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

Modular Tetration

Examples