Consider a rectangular parallelepiped with sides $a$, $b$, and $c$, that consists of unit cubes of $k$ different colors. We can apply cyclic shifts to the parallelepiped in any of the three directions any number of times$^{\text{∗}}$.

There are $d_i$ cubes of the $i$-th color ($1 \le i \le k$). How many different parallelepipeds (with the given sides) can be formed from these cubes, no two of which can be made equal by some combination of cyclic shifts?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains four integers: $a$, $b$, $c$, and $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$) — three sides of the parallelepiped and the number of colors of unit cubes.

The second line of each test case contains $k$ integers $d_1, d_2, \ldots, d_k$ ($1 \le d_1 \le d_2 \le \ldots \le d_k \le 3 \cdot 10^6$) — the elements of the array $d$: the number of cubes of a given color.

It is guaranteed that in each test case the sum of the elements of the array $d$ is equal to $a \cdot b \cdot c$.

It is guaranteed that the sum of $k$ over all test cases does not exceed $10 ^ 6$.

Output

For each test case, print one integer — the number of different parallelepipeds modulo $998\,244\,353$.

见题面 Input 部分

见题面 Output 部分

In the first test case, there is only one parallelepiped, which consists of one unit cube.

Possible parallelepipeds in the second test case