题目背景

“等下，米尔嘉，你是什么时候拿到这道题的啊？”我问道。
“是中午我去老师办公室的时候，你现在就在这里从零开始思考吧。我到那边去想，再见。”米尔嘉朝我挥挥手，优雅的移到窗边的座位上。我的目光紧紧的追随着米尔嘉，透过窗户，我可以看到凋零的梧桐树，梧桐树的上面是广阔的冬季的蓝天，虽然是个晴天，但是外面看上去还是很冷。

题目描述

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

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

输入格式

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

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

输出格式

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

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

提示

样例解释

第一个例子中的 $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$。