8693: BZOJ4693:雪中送温暖

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

每年的1月10日是温暖节,在这一天,化身出题人的C_SUNSHINE将会给OIer们送温暖。OIer们只要在门口放上一个 仙人掌,就能在早上的某个时刻听到门外传来一声:“开门,送温暖——”作为一个萌萌哒OIer,Salroey从C_SUN SHINE那里收到了一个令人感到温暖的问题,她想与你分享分享。有一个K维空间,每个整点上都有一个信号灯,每 个信号灯的位置都可以由K 个整数(x1,x2...xk) 表示,信号灯的颜色定义如下: 1.如果存在i满足xi=0则(x1,x2...xk) 为绿色。 2.如果对于所有i满足xi=1 则 (x1,x2...xk)为红色。 3.对于信号灯(x1,x2...xk) ,定义它的k 个前驱为恰好某一维的坐标比这个信号灯恰好少1 其余坐标都与这个信号灯相等的信号灯,即(x1,x2..xi-1,xi+1...xk) 。如果这些前驱中有偶数个红灯 则这个信号灯为绿色,否则为红色。 现在给定k 和一个k 维矩形,求矩形内部红灯数目,包括边界。


输入格式

第一行一个正整数t 表示数据组数,对于每组数据: 第一行一个整数k 。 第二行 2k个整数L1,L2..Lk,R1,R2...Rk 描述一个矩形的两个顶点。 T<=10,1<=k<=9,1<=Li<=Ri<=10^15


输出格式

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


样例输入

2
1
1 3
2
1 2 3 4

样例输出

3
5

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: