信息学奥赛题库- 修墙

友情提示：380元/半年，儿童学编程，就上码丁实验室。

【题目描述】

在地图上，土地可以大致用一个无限大的黑白二维矩阵表示，其中用户为白格，墙为黑格。由于墙很高，两个用户能够互相通信当且仅当在网格上这两个白格能够只经过四联通的白格相互到达。

经过一番细致的研究，发现这个地图可以由如下过程迭代构造。

地图上一开始只有一个白格。

一次迭代中，假设原来的地图为$A$，那么新的地图为

AA
AB

其中$B$为一个与$A$边长相同且全为黑格的正方形矩阵。

例如三次迭代之后，我们得到了这样一个矩阵($W$表示白格，$B$表示黑格):

经过无限次迭代之后，我们就得到了土地对应的黑白矩阵。

无限大的地图，分析起来过于困难。每次会截出一个子矩阵，他想要知道这个子矩阵中的用户在墙的阻隔下组成了多少个联通块，联通块定义为极大的能够互相通信的用户集合。

由于一次询问不足以分析，需要进行$q$次询问。

【输入】

第一行一个正整数$q$。

接下来$q$行每行四个正整数$x_1,y_1,x_2,y_2(1≤x_1≤x_2,1≤y_1≤y_2)$，表示询问以第$x_1$行第$y_1$列，第$x_2$行第$y_2$列为两对角的矩形内用户形成的联通块数。

【输出】

$q$行，每行一个正整数，表示对应矩形内的联通块数量。

【输入样例】

4
1 1 5 5
2 2 3 6
4 2 7 5
2 2 2 2

【输出样例】

1
3
3
0

【提示】

需要注意的是如果矩形内没有用户应该输出$0$。