这题中，我们要先来定义一系列的二维 pattern Pi。 Pi 的大小为内有 2i x 2i 格的正方形，每一格必定是黑白其中的一种颜色。 P0 为 1 x 1 的 pattern，唯一的一格是黑色的。对于大于0 的i，我们用递归的方式定义Pi，首先，我们将Pi 以田字型分割成四块2i-1x 2i-1的子正方形。其中，右上角的子正方形中，所有的格子都是白色的，而其余的三个子正方形，其颜色的分布都恰好跟 Pi-1一样。 举例而言，下面展示出 P0 至 P2 的样子，B 为黑色的格子，W 为白色的格子： P0: B P1: BW BB P2: BWWW BBWW BWBW BBBB 现在，让我们考虑 P∞。在这个 pattern 中，我们定义其最左下角的一个格子的座标为 (0, 0)，x 轴的正向往右，而 y 轴的正向往上。 请问， P∞内，左下角座标为 (a, b) 且宽度为 w，高度为 h 的矩形范围中，有多少个四联通的黑色联通块呢？ 四联通的定义为：两个格子必须要有共同的边才能算做联通。

输入描述:

输入的第一行有一个正整数Q，代表接下来有几组询问。接下来的Q行每行有四个整数a, b, w, h，代表一个询问。

输出描述:

对于每一组询问，请在一行中输出一个整数，代表这个询问的答案。

备注:

1≤Q≤1.6×1050≤a,b311≤w,h31