Le professeur Pang possède $n$ rectangles. Les coordonnées du coin inférieur gauche du $i$-ième rectangle sont $(x_{i,1}, y_{i,1})$, et les coordonnées du coin supérieur droit sont $(x_{i,2}, y_{i,2})$. Les rectangles peuvent se chevaucher.

Vous devez choisir trois droites telles que :

• Chaque droite soit parallèle à l'axe des $x$ ou à l'axe des $y$, ce qui signifie que son équation est de la forme $x = a$ ou $y = a$.
• Dans l'équation $x = a$ ou $y = a$, $a$ doit être un entier dans $[1, 10^9]$.
• Ces trois droites doivent être distinctes.
• Chaque rectangle soit touché par au moins une droite. Une droite touche un rectangle si elle intersecte la frontière et/ou l'intérieur du rectangle.

Vous devez calculer le nombre de façons de choisir ces trois droites. Comme le résultat peut être très grand, donnez-le modulo 998244353. Deux façons sont considérées comme identiques si seul l'ordre des trois droites diffère.

Entrée

La première ligne contient un entier unique $T$ ($1 \le T \le 10^5$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 10^5$). Chacune des $n$ lignes suivantes contient quatre entiers $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}$ ($1 \le x_{i,1} < x_{i,2} \le 10^9$, $1 \le y_{i,1} < y_{i,2} \le 10^9$).

Il est garanti que la somme de $n$ sur tous les cas de test n'excède pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez un entier représentant la réponse sur une ligne.

Exemples

Entrée 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

Sortie 1

230616300
64
977066618