“五行”是中国传统文化中用于解释多种现象的五种概念，即火、水、木、金、土。它们之间存在两种基本的相互作用，每种作用都形成一个循环。

相生循环为： • 木 → 火 → 土 → 金 → 水 → 木

相克循环为： • 木 → 土 → 水 → 火 → 金 → 木

大魔法师 Yukikaze 正在设计基于五行的魔法。通过嵌入复杂的几何图案，她可以调整注入魔法的每种元素的量。我们使用五个整数参数来描述 Yukikaze 发明的魔法，即每种元素注入的量。

她有四种扰动方法来按需修改魔法的参数：

单元素调整：增加或减少某一种元素的量 1。

正向传播调整：增加元素 $x$ 的量 1。如果存在 $x$ 生 $y$ 且 $y$ 生 $z$，则 $y$ 和 $z$ 的量也增加 1。或者减少元素 $x$ 的量 1。如果存在 $x$ 生 $y$ 且 $y$ 生 $z$，则 $y$ 和 $z$ 的量也减少 1。

负向传播调整：增加元素 $x$ 的量 1。如果存在 $x$ 生 $y$ 且 $y$ 克 $z$，则 $y$ 的量增加 1，且 $z$ 的量减少 1。或者减少元素 $x$ 的量 1。如果存在 $x$ 生 $y$ 且 $y$ 克 $z$，则 $y$ 的量减少 1，且 $z$ 的量增加 1。

全局调整：增加或减少所有元素的量 1。

例如，金生水，水生木。通过增加金的量 1 来应用正向传播调整，结果是金、水、木的量都增加了 1。再如，火生土，土克水。通过减少火的量 1 来应用负向传播调整，结果是火和土的量都减少了 1，而水的量增加了 1。

Yukikaze 想要创造一些新奇的魔法。初始时，五个参数均为零。现在给定描述魔法的五个参数以及她想要使用的步数，她想知道通过上述扰动方法，在每一步恰好使用一种扰动方法的情况下，有多少种方法可以创造出该魔法。如果存在某个整数 $i$，使得第 $i$ 步所使用的方法不同，则认为两种方法不同。由于答案可能非常大，请输出答案对 998244353 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示 Yukikaze 想要创造的魔法数量。

接下来的 $T$ 行，每行包含六个整数 $c_{\text{Wood}}, c_{\text{Fire}}, c_{\text{Earth}}, c_{\text{Metal}}, c_{\text{Water}}$ ($-10^5 \le c_{\text{Wood}}, c_{\text{Fire}}, c_{\text{Earth}}, c_{\text{Metal}}, c_{\text{Water}} \le 10^5$) 和 $k$ ($0 \le k \le 10^5$)，分别表示魔法的五个参数以及 Yukikaze 想要使用的步数。

输出格式

对于每个魔法，输出创造它的方法数，对 998244353 取模。

样例

输入 1

5
0 0 0 0 0 1
0 0 0 3 2 5
1 1 1 1 1 5
3 2 1 1 1 4
0 -1 0 2 4 5

输出 1

0
10000
100000
576
2500