题目描述

每年的1月10日是温暖节，在这一天，化身出题人的 C_SUNSHINE 将会给 OIer 们送温暖。OIer 们只要在门口放上一个仙人掌，就能在早上的某个时刻听到门外传来一声：“开门，送温暖——”。作为一个萌萌哒 OIer，Salroey 从 C_SUNSHINE 那里收到了一个令人感到温暖的问题，她想与你分享。有一个 K 维空间，每个整点上都有一个信号灯，每个信号灯的位置都可以由 K 个整数 $(x_1, x_2, \ldots, x_k)$ 表示，信号灯的颜色定义如下：

1. 如果存在 $i$ 满足 $x_i=0$ 则 $(x_1, x_2, \ldots, x_k)$ 为绿色。
2. 如果对于所有 $i$ 满足 $x_i=1$ 则 $(x_1, x_2, \ldots, x_k)$ 为红色。
3. 对于信号灯 $(x_1, x_2, \ldots, x_k)$ ，定义它的 $k$ 个前驱为恰好某一维的坐标比这个信号灯恰好少 1 其余坐标都与这个信号灯相等的信号灯，即 $(x_1, x_2, \ldots, x_{i-1}, x_{i+1}, \ldots, x_k)$ 。如果这些前驱中有偶数个红灯则这个信号灯为绿色，否则为红色。 现在给定 $k$ 和一个 $k$ 维矩形，求矩形内部红灯数目，包括边界。

输入格式

每个输入包含多组数据。 第一行一个正整数 $t$ 表示数据组数，对于每组数据：

• 第一行一个整数 $k$ 。
• 第二行 $2k$ 个整数 $L_1, L_2, \ldots, L_k, R_1, R_2, \ldots, R_k$ 描述一个矩形的两个顶点。$T \leq 10, 1 \leq k \leq 9, 1 \leq L_i \leq R_i \leq 10^{15}$

输出格式

对于每组数据输出一个整数表示红灯的数目，答案对 $998244353$ 取模。

输入数据示例

2
1
1 3
2
1 2 3 4

输出数据示例

3
5