Problem Description

As a great alchemist, Sophie learns Discrete Mathematics very well.

One day, Sophie finds a magic prime number $p$. From her grandma's teaching, if a polynomial $F(x)$ satisfying that $F(x) \equiv 0 \pmod p$ has a solution, then the polynomial is mysterious.

To understand the property of mysterious polynomials, Sophie studies the roots of polynomial.

Given integer $n$, prime number $p$ and parameter $c \in \mathbb{F}_p$, the set $S \subseteq \mathbb{F}_p$ is good, if there exist polynomial $f(x),g(x) \in \mathbb{F}_p[x]$ satisfying
<ol>
<li> $\mathrm{deg}(f) = n$ </li>
<li> $g(x)\mid f(x)$, i.e., $g(x)$ divides $f(x)$ </li>
<li> Call $T$ the set of roots of polynomial $h(x) = f(x)g(c \cdot x)$, then $S = T\;\cap \mathbb{F}_p$ </li>
</ol>

Sophie wonders the number of good sets given $n,p$ and $c$. Since the answer may be too large, you should output the answer modulo $998244353$.

If you are not familiar with those notations, please refer to the ``Notes section'' in the pdf statement for formal definition.

Input

The first line contains an integer $T(T\geq 1)$, denoting the number of test cases.

For each test case, there is a line containing three integers $p, c, n(1 \leq c \lt p \leq 5*10^5, 0 \leq n \leq 10^6)$, whose meaning is already given in the previous statement.

It is guaranteed that the sum of $p$ over all test cases won't exceed $10^7$.

Output

For each test case, output an integer in a line, denoting the answer taken modulo $998244353$.

2
3 2 2
5 4 2

8
23