F. 立方体的数量
每个测试的时间限制：5 秒
内存限制：256 兆字节

考虑一个边长为 $a$、$b$、$c$ 的长方体，它由 $k$ 种不同颜色的单位立方体组成。我们可以对长方体在三个方向上任意进行循环移位任意多次 $^*$。

颜色 $i$ 的立方体有 $d_i$ 个（$1 \le i \le k$）。问：用这些立方体可以组成多少个不同的长方体（给定边长），使得任意两个长方体不能通过若干次循环移位变得相同？

$^*$ 如图所示：

• 左上角：原始长方体的俯视图。下层将与顶层以相同方式移位。
• 右上角：长方体向右移动 $1$ 格后的俯视图。
• 左下角：长方体向下移动 $2$ 格后的俯视图。
• 右下角：长方体向右移动 $1$ 格、向下移动 $2$ 格后的俯视图。
  

输入

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 100$）。

每个测试用例的描述如下：

• 第一行包含四个整数：$a$、$b$、$c$、$k$（$1 \le a,b,c \le 3 \cdot 10^6$；$a \cdot b \cdot c \le 3 \cdot 10^6$；$1 \le k \le 10^6$）—— 长方体的三边长度和颜色数量。
• 第二行包含 $k$ 个整数 $d_1, d_2, \dots, d_k$（$1 \le d_1 \le d_2 \le \dots \le d_k \le 3 \cdot 10^6$）—— 颜色 $i$ 的立方体数量。

保证每个测试用例中 $d$ 数组的元素之和等于 $a \cdot b \cdot c$。
保证所有测试用例的 $k$ 之和不超过 $10^6$。

输出

对于每个测试用例，输出一个整数 —— 不同长方体的数量，对 $998244353$ 取模。

示例

输入：

6
1 1 1 1
1
6 1 1 3
1 2 3
12 1 1 3
2 4 6
3 3 1 2
3 6
2 3 3 2
6 12
72 60 96 4
17280 86400 120960 190080

输出：

1
10
1160
12
1044
231490207

注释

• 第一个测试用例：只有一个长方体，由一个单位立方体组成。
• 第二个测试用例的可能长方体见原题说明。