题目描述

一座城市被抽象为平面直角坐标系，其中划分了 $n$ 个需要巡检的矩形区域。所有区域的边都与坐标轴平行，第 $i$ 个区域的左下角为 $(x_{i,1},y_{i,1})$，右上角为 $(x_{i,2},y_{i,2})$。不同区域之间允许重叠。

现在需要规划三条无限延伸的直线巡检航线，并满足以下要求：

• 每条航线都与某一条坐标轴平行，且其固定坐标必须是整数。换言之，航线方程只能是 $x=a$ 或 $y=a$，其中 $a$ 是 $[1,10^9]$ 范围内的整数；
• 三条航线必须两两不同；
• 每个矩形巡检区域都至少与一条航线相交。航线穿过区域内部或与区域边界重合，均视为相交。

一组方案由选出的三条航线确定。请统计能够覆盖全部巡检区域的方案数量，并将答案对 $998\,244\,353$ 取模。

输入格式

第一行一个整数 $T$ ，表示数据组数。

每组数据第一行一个整数 $n$ ，表示矩形的数量。

接下来 $n$ 行，每行四个整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$ ，表示一个矩形的顶点坐标。

输出格式

每组数据输出一行，一个整数答案。

样例

样例1

样例输入

3
1
1 1 1000000000 1000000000
3
1 1 2 2
3 3 4 4
5 5 6 6
5
581574116 47617804 999010750 826131769
223840663 366320907 613364068 926991396
267630832 51913575 488301124 223957497
217461197 492085159 999485867 913732845
28144453 603781668 912516656 993160442

样例输出

230616300
64
977066618

数据范围与提示

本题采用子任务捆绑测试。

子任务 $1$ （ $2$ 分）： $n=1$ ， $\sum n\leq 200$ ；
子任务 $2$ （ $8$ 分）： $n=2$ ， $\sum n\leq 200$ ；
子任务 $3$ （ $15$ 分）： $n\leq 100$ ， $\sum n\leq 200$ ， $x_{i,2},y_{i,2}\leq 10$ ；
子任务 $4$ （ $25$ 分）： $n\leq 100$ ， $\sum n\leq 200$ ；
子任务 $5$ （ $13$ 分）： $x_{i,1}$ 都相等， $x_{i,2}$ 都相等；
子任务 $6$ （ $17$ 分）： $x_{i,1}$ 都相等；
子任务 $7$ （ $20$ 分）：无特殊限制。

所有数据： $1\le T\leq 10^5$ ， $1\leq n\leq 10^5$ ， $1\leq x_{i,1}\lt x_{i,2}\leq 10^9$ ， $1\leq y_{i,1}\lt y_{i,2}\leq 10^9$ ， $\sum n\leq 2\times 10^5$ 。