Problem Visual

Problem Statement

There are $3$ points $A, B, C$ in $xyz$ space. The coordinates of $A, B, C$ are $(a_x, a_y, a_z), (b_x, b_y, b_z), (c_x, c_y, c_z)$, respectively.

Let $S$ be the area of the shadow of triangle $ABC$ on the $xy$ plane cast by a point light source located at coordinates $(l_x, l_y, l_z)$. If the shadow is a line segment or a point, let $S = 0$.

Find $S \pmod{998244353}$.

Solve $T$ test cases.

Notes

Under the constraints of this problem, it can be proved that there exists a pair of integers $(\alpha, \beta)$ satisfying the following.

• $\beta$ is not a multiple of $998244353$.
• $\beta \times S = \alpha$.

For a pair of integers $(\alpha, \beta)$ satisfying this condition, there exists exactly one integer $\gamma$ satisfying $$\beta \times \gamma \equiv \alpha \pmod{998244353}$$ that is at least $0$ and less than $998244353$. Using this integer $\gamma$, we define $S \pmod{998244353} := \gamma$.

Note that although there can be many pairs of integers $(\alpha, \beta)$ satisfying the condition, it can be proved that $\gamma$ does not depend on the choice of $\alpha, \beta$ and is determined only by $E$.

Constraints

• $1 \leq T \leq 10^5$.
• Constraints for each test case
  • $\lvert a_x \rvert \leq 10^6$
  • $\lvert b_x \rvert \leq 10^6$
  • $\lvert c_x \rvert \leq 10^6$
  • $\lvert a_y \rvert \leq 10^6$
  • $\lvert b_y \rvert \leq 10^6$
  • $\lvert c_y \rvert \leq 10^6$
  • $1 \leq a_z \leq 10^6$
  • $1 \leq b_z \leq 10^6$
  • $1 \leq c_z \leq 10^6$
  • $\lvert l_x \rvert \leq 10^6$.
  • $\lvert l_y \rvert \leq 10^6$.
  • $1 \leq l_z \leq 10^6$.
  • $\max(a_z, b_z, c_z) \leq l_z$
  • $A, B, C$ are not $3$ collinear points.
• All input values are integers.

Input

$T$
${\rm Testcase}_1$
$\vdots$
${\rm Testcase}_T$

Each test case is given in the following format.

$a_x$ $a_y$ $a_z$
$b_x$ $b_y$ $b_z$
$c_x$ $c_y$ $c_z$
$l_x$ $l_y$ $l_z$

Output

The output consists of $T$ lines. On line $t~(1 \leq t\leq T)$, print the answer for test case $t$.

Do not forget the newline at the end as well.

Sample

3
9 -2 3
3 0 4
4 5 2
1 2 5
3 -1 3
0 9 4
7 -3 9
13 -6 18
8 29 2001
8 18 2004
2 17 2003
4 6 4646

75
0
917747442