Description

现在有一张 $a\times a$ 的网格，每个格子只能是黑色或白色。
请问：对于其中每个 $b\times b$ 的网格，都恰好有 $n$ 个格子是黑色的颜色分布方案有几种？
为了不让题目太难，米尔嘉只需要你解决 $n\in\{1,2\}$ 的情况即可。

由于答案可能很大，你只需要输出方案数对 $998244353$ 取模后的结果就可以了。

Input Format

本题有多组数据，第一行输入一个整数 $T$，表示数据组数。

对于每一组询问，我们给出 $a,b,n$。

Output Format

对于每组数据，一行输出一个数表示取模后的方案数。

8
3 2 1
10 3 1
100 3 1
1145141919810 23333333 1
3 2 2
10 3 2
100 3 2
1145141919810 23333333 2

8
261
792303199
491969808
14
16316
968654202
961966479

Hint

样例解释

第一个例子中的 $8$ 种方案分别是：

第三个例子取模前的结果是：$55590605665555221$

数据范围

对于 $100\%$ 数据，保证 $T\in[1,10^5],n\in\{1,2\},1\le n\le b^2\le a^2\le (10^{18})^2$。