题目描述

小 L 来到了与之国游玩。与之国的国土是无限大的，可以认为是坐标系的一个象限。

把与之国的国土分别按照两维等距离划分，则每一块小正方形都有编号 \((x,y),0\leq x,y\)，并且与之国的地形非常特殊，如果 \(x~\text{and}~y=0\)，（其中 \(\text{and}\) 表示按位与）则这块地是陆地，否则是海洋。

小 L 有一些问题，每个问题形如如果只保留满足 \(l_x\leq x\leq r_x,l_y\leq y\leq r_y\) 的国土，陆地形成了几个**四连通块**。

注：四连通块指上下左右四个方向能连通的连通块。

输入格式

第一行一个整数 \(n\) 表示问题个数。

接下来 \(n\) 行，每行四个整数 \(l_x,l_y,r_x,r_y\)，表示询问区域。

输出格式

\(n\) 行，每行一个整数，表示连通块个数。

样例输入1

3
1 1 2 2
0 1 3 3
2 2 2 2

样例输出1

2
2
0

样例输入输出2

见下发文件。

样例解释

样例1前2行询问的解释（黄色表示 \(x~\text{and}~y=0\)）：

第一行询问：1 1 2 2 如下图所示，其中（1，2）是一个连通块， （2，1）是一个连通块，共2个连通块

第二行询问：0 1 3 3 如下图所示，（0，1）（0，2）（0，3）和（1，2）组成一个连通块，（2，1）自己是一个连通块，共2个连通块

数据规模

共10个测试点。

测试点\(1,2\)满足\(n\leq 1, 0 \leq l_x,r_x\lt 2^{11},0 \leq l_y \leq r_y \lt 2^{11}\)。

测试点\(3, 4\)满足\(n\leq 10^4,0 \leq l_x,r_x\lt 2^{11},0 \leq l_y \leq r_y \lt 2^{11}\)。

测试点\(5, 6\)满足\(l_x=l_y=0\)。

测试点\(7, 8\)满足\(l_x=r_x\)。

对于所有数据，满足\(1\leq n\leq 10^5,0\leq l_x\leq r_x\lt 2^{30},0\leq l_y\leq r_y\lt 2^{30}\)。

下发文件

ssfz联测 下发文件