問題ヴィジュアル

問題文

$xyz$ 空間上に $3$ 点 $A, B, C$ がある. $A, B, C$ の座標はそれぞれ $(a_x, a_y, a_z), (b_x, b_y, b_z), (c_x, c_y, c_z)$ である.

座標 $(l_x, l_y, l_z)$ にある点光源によって作られる三角形 $ABC$ の $xy$ 平面における影の面積を $S$ とする. ただし, 影が線分や点になる場合は $S = 0$ とする.

このとき, $S \pmod{998244353}$ を求めよ.

$T$ 個のテストケースについて答えよ.

注記

この問題の制約下では, 以下を満たすような整数の組 $(\alpha, \beta)$ が存在することが証明できる.

• $\beta$ は $998244353$ の倍数ではない.
• $\beta \times S = \alpha$.

この条件を満たすような整数の組 $(\alpha, \beta)$ に対して, $$\beta \times \gamma \equiv \alpha \pmod{998244353}$$ となる $0$ 以上 $998244353$ 未満の整数 $\gamma$ が唯一存在する. この整数 $\gamma$ を用いて, $S \pmod{998244353} := \gamma$ と定義する.

なお, 条件を満たすような整数の組 $(\alpha, \beta)$ は数多に考えられるが, $\gamma$ は $\alpha, \beta$ の取り方に依らず, $E$ のみによって決まることが証明できる.

制約

• $1 \leq T \leq 10^5$.
• 各テストケース毎の制約
  • $\lvert a_x \rvert < 10^6$
  • $\lvert b_x \rvert < 10^6$
  • $\lvert c_x \rvert < 10^6$
  • $\lvert a_y \rvert < 10^6$
  • $\lvert b_y \rvert < 10^6$
  • $\lvert c_y \rvert < 10^6$
  • $1 \leq a_z < 10^6$
  • $1 \leq b_z < 10^6$
  • $1 \leq c_z < 10^6$
  • $\lvert l_x \rvert < 10^6$.
  • $\lvert l_y \rvert < 10^6$.
  • $1 \leq l_z < 10^6$.
  • $\max(a_z, b_z, c_z) < l_z$
  • $A, B, C$ は同一直線上の $3$ 点ではない.
• 入力は全て整数である.

入力

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

各テストケースは以下の形式である.

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

出力

出力は $T$ 行からなる. 第 $t~(1 \leq t\leq T)$ 行には, 第 $t$ テストケースにおける解答を出力せよ.

最後にも改行を忘れないこと.

サンプル

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