Prof. Pang は $n$ 個の長方形を持っています。$i$ 番目の長方形の左下の座標は $(x_{i,1}, y_{i,1})$ であり、右上の座標は $(x_{i,2}, y_{i,2})$ です。長方形同士は重なっている可能性があります。

あなたは以下の条件を満たすように 3 本の直線を引く必要があります。

• 各直線は $x$ 軸または $y$ 軸に平行であること。つまり、式は $x = a$ または $y = a$ の形であること。
• 式 $x = a$ または $y = a$ において、$a$ は $[1, 10^9]$ の範囲の整数であること。
• これら 3 本の直線は互いに異なること。
• すべての長方形は、少なくとも 1 本の直線に触れていること。直線が長方形に触れるとは、その直線が長方形の境界および／または内部と交差することを指します。

3 本の直線を選ぶ方法の数を計算してください。答えは非常に大きくなる可能性があるため、998244353 で割った余りを出力してください。3 本の直線の順序のみが異なる選び方は、同一のものとみなします。

入力

入力の最初の行には、テストケースの数を示す整数 $T$ ($1 \le T \le 10^5$) が含まれます。 各テストケースの最初の行には、整数 $n$ ($1 \le n \le 10^5$) が含まれます。続く $n$ 行の各行には、4 つの整数 $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 行で出力してください。

入出力例

入力 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