作为一名伟大的炼金术士，Sophie 对离散数学有着深刻的理解。

有一天，Sophie 发现了一个神奇的素数 $p$。根据她祖母的教导，如果一个满足 $F(x) \equiv 0 \pmod p$ 的多项式 $F(x)$ 存在解，那么这个多项式就是“神秘的”。

为了理解神秘多项式的性质，Sophie 研究了多项式的根。

给定整数 $n$、素数 $p$ 和参数 $c \in \mathbb{F}_p$，如果存在多项式 $f(x), g(x) \in \mathbb{F}_p[x]$ 满足以下条件，则称集合 $S \subseteq \mathbb{F}_p$ 是“好的”：

• $\deg(f) = n$；
• $g(x) \mid f(x)$，即 $g(x)$ 整除 $f(x)$；
• 令 $T$ 为多项式 $h(x) = f(x)g(c \cdot x)$ 的根集，则 $S = T \cap \mathbb{F}_p$。

Sophie 想知道在给定 $n, p$ 和 $c$ 的情况下，有多少个好的集合。由于答案可能非常大，你需要输出答案对 $998244353$ 取模的结果。

如果你不熟悉这些符号，请参考“说明”部分获取正式定义。

输入格式

第一行包含一个整数 $T(T \ge 1)$，表示测试用例的数量。

对于每个测试用例，包含一行三个整数 $p, c, n(1 \le c < p \le 5 \times 10^5, 0 \le n \le 10^6)$，其含义已在上述说明中给出。

保证所有测试用例中 $p$ 的总和不超过 $10^7$。

输出格式

对于每个测试用例，输出一行一个整数，表示答案对 $998244353$ 取模的结果。

样例

输入 1

2
3 2 2
5 4 2

输出 1

8
23

说明

给定素数 $p$，$\mathbb{F}_p = \{0, 1, 2, \dots, p - 1\}$ 是模运算下的整数集合，且 $\mathbb{F}_p[x] = \{f(x) = \sum_{i=0}^n a_i x^i \mid a_0, a_1, \dots, a_n \in \mathbb{F}_p\}$。

多项式 $f(x) = \sum_{i=0}^n a_i x^i \in \mathbb{F}_p[x]$ 的次数为 $n$ 当且仅当 $a_n \neq 0$。我们规定零多项式 $h(x) \equiv 0$ 的次数为 $-\infty$。

多项式 $f(x) = \sum_{i=0}^n f_i x^i$ 整除 $g(x)$ 当且仅当存在多项式 $h(x)$ 满足 $f(x) = g(x) \cdot h(x)$，即对于所有 $k \ge 0$，$f(x)$ 的第 $k$ 次项系数等于 $g(x) \cdot h(x)$ 的第 $k$ 次项系数。