题目描述

考虑 $K$ 维空间上的每个整点，我们用 $P_i$ 表示点 $P$ 的第 $i$ 维坐标。称点 $P$ 是点 $Q$ 的前驱，当且仅当存在一个 $i$ 满足：

$P_i = Q_i - 1, \forall j \neq i, P_j = Q_j$ 定义一个点为关键点当且仅当它的前驱中恰有奇数个关键点。特别地，我们钦定 $(1, 1, 1 ... 1)$ 是关键点，也就是说满足 $\forall i, P_i = 1$ 的点 $P$ 是关键点。

现在对于每个维度给定一个区间 $[L_i, R_i]$ ，求每个维度都在给定区间内的关键点的数量，对 $998244353$ 取模。

输入格式

第一行 $T$ 表示数据组数。

对于每组数据，第一行一个整数表示 $K$ ，第二行 $2K$ 个整数表示 $L_1, L_2 ... L_K, R_1, R_2 ... R_K$ 。

$T \le 10$

$K \le 9$

$1 \le L_i \le R_i \le 2 \times 10^{15}$

输出格式

每组数据一行一个整数表示答案。

样例输入1

2

1

1 3

2

1 2 3 4

样例输出1

3

5

这题其实放组合数学也行，放状压DP也行，放数位DP也不是不行。