#218 Yet Another Angular Sort Problem

Statement

Statement language

There are $N$ distinct points $A_1,A_2,\cdots,A_N$ in the plane, and no three of them are collinear. A line $\ell$ passing through none of the points is also given. A point $P$ moves along $\ell$ from infinity on one side to infinity on the other side.

At every moment, sort $A_1,A_2,\cdots,A_N$ around . Starting from a ray parallel to in one fixed direction, list the point indices encountered clockwise. Call the resulting permutation .

The permutation may change several times. If $Q$ and $Q'$ are the permutations immediately before and after one change, define its amount as

\sum_{i=1}^{N}|Q_i-Q'_i|.

Find the sum of the amounts of all changes modulo $998\,244\,353$ .

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the sum of all change amounts modulo $998\,244\,353$ .

Constraints

$1 \leq T \leq 100$
$1 \leq N \leq 300\,000$
$- 10^{9} \leq a, b,$

Subtasks

#	Score	Constraints
1	25	$N \leq 500$ , and the sum of $N^2$ over all test cases does not exceed $200\,000$ .
2	75	No additional constraints.

Samples

Input

Output

8