与之国(and) 1s 128MB O2 加速

问题描述

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

把与之国的国土分别按照两维等距离划分,则每一块小正方形都有编号

(x, y), 0 <= x, y,并且与之国的地形非常特殊,如果x and y = 0,其中and 表示按 位与,则这块地是陆地,否则是海洋。

小 L 有一些问题,每个问题形如如果只保留满足lx <= x <= rx , ly <= y <= ry 的国土, 陆地形成了几个四连通块。

输入格式

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

接下来 n 行,每行四个整数 lx , ly , rx , ry ,表示询问区域。

输出格式

n 行,每行一个整数,表示连通块个数。

样例输入1

3

1 1 2 2

0 1 3 3

2 2 2 2

样例输出1

2

2

0

样例输入输出2

见下发文件。

数据规模

共 10 个测试点。

测试点1,2满足n <= 1,0 <= lx <= rx < 211, 0 <= ly <= ry < 211。

测试点3,4满足n <= 104, 0 <= lx <= rx < 211, 0 <= ly <= ry < 211。

测试点5,6满足lx = ly = 0。

测试点7,8满足lx = rx。

对于所有数据,满足1 <= n <= 105, 0 <= lx <= rx < 230, 0 <= ly <= ry < 230。