Prof. Pang은 $n$개의 직사각형을 가지고 있으며, $i$번째 직사각형의 왼쪽 아래 모서리 좌표는 $(x_{i,1}, y_{i,1})$이고 오른쪽 위 모서리 좌표는 $(x_{i,2}, y_{i,2})$입니다. 직사각형들은 서로 겹칠 수 있습니다.

다음 조건을 만족하는 세 개의 직선을 선택해야 합니다.

• 각 직선은 $x$축 또는 $y$축에 평행해야 하며, 즉 직선의 방정식은 $x = a$ 또는 $y = a$ 꼴이어야 합니다.
• 방정식 $x = a$ 또는 $y = a$에서 $a$는 $[1, 10^9]$ 범위의 정수여야 합니다.
• 이 세 직선은 서로 달라야 합니다.
• 각 직사각형은 적어도 하나의 직선에 닿아야 합니다. 직선이 직사각형에 닿는다는 것은 직선이 직사각형의 경계 및/또는 내부와 교차함을 의미합니다.

세 직선을 선택하는 방법의 수를 계산해야 합니다. 답이 매우 클 수 있으므로, $998244353$으로 나눈 나머지를 출력하십시오. 세 직선의 순서만 다른 경우 두 방법은 같은 것으로 간주합니다.

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^5$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$ ($1 \le n \le 10^5$)이 주어집니다. 이어지는 $n$개의 줄에는 각 직사각형을 나타내는 네 개의 정수 $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$)가 주어집니다.

모든 테스트 케이스에 대한 $n$의 합은 $2 \times 10^5$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 문제의 답을 한 줄에 하나씩 출력하십시오.

예제

입력 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

출력 1

230616300
64
977066618