A 四叉树 是一种树形数据结构,其中每个节点最多有四个子节点,并占据一个正方形区域。
正式地, 对于所有元组 非负整数 $$$k,a,b \ge 0$$$,存在 正好一个节点 占以下区域$$$^{\text{*}}$$$。
$$[a \cdot 2^k,(a+1) \cdot 2^k] \times [b \cdot 2^k,(b+1) \cdot 2^k]$$
区域大于 $$$1 \times 1$$$ 的所有节点都包含四个子节点,对应于均分为四的区域,区域为 $$$1 \times 1$$$ 的节点对应于树的叶节点。
显示了节点所占区域的一小部分。相对较暗的区域更靠近叶节点。 主唱讨厌这种广泛存在的误解,即当区域内存在 $$$n$$$ 叶节点时,四叉树可以在 $$$\mathcal{O}(\log n)$$$ 时间内执行范围查询。事实上,有时为此需要查询的区域远多于 $$$\mathcal{O}(\log n)$$$,在某些极端情况下,时间复杂度为 $$$\mathcal{O}(n)$$$。因此,主唱提出了这个任务来让您了解数据结构的这种最坏情况。
粉色士兵给了你一个有限区域 $$$[l_1,r_1] \times [l_2,r_2]$$$,其中 $$$l_i$$$ 和 $$$r_i$$$ ($$$l_i \lt r_i$$$) 是非负整数。请找出必须选择的最小节点数,以便使所选节点所占的区域并集 正是 与给定区域相同。这里,如果存在一个点包含在一组点中但不包含在另一组点中,则认为两组点是不同的。
$$$^{\text{*}}$$$区域是点的集合 具有真实坐标,其中点 $$$(x,y)$$$ 包含在区域 $$$[p,q] \times [r,s]$$$ 当且仅当 $$$p \le x \le q$$$ 和 $$$r \le y \le s$$$ 中。这里,$$$\times$$$ 正式指的是集合的笛卡尔积。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含四个整数 $$$l_1$$$、$$$r_1$$$、$$$l_2$$$、$$$r_2$$$ - 每个轴上区域的边界 ($$$0 \le l_i \lt r_i \le 10^6$$$)。
输出
对于每个测试用例,在单独的行上输出满足条件所需的最小节点数。
示例
输入复制
50 1 1 20 2 0 21 3 1 30 2 1 59 98 244 353
输出复制
1 1 4 5 374
注意
在第一个测试用例中,给定区域为 $$$[0,1] \times [1,2]$$$。有一个节点占 $$$[0,1] \times [1,2]$$$。选择这个节点,答案是$$$1$$$。
在第二个测试用例中,给定区域为 $$$[0,2] \times [0,2]$$$。有一个节点占 $$$[0,2] \times [0,2]$$$。选择这个节点,答案是$$$1$$$。
在第三个测试用例中,给定区域为 $$$[1,3] \times [1,3]$$$。有 没有节点 占 $$$[1,3] \times [1,3]$$$。相反,您可以通过选择以下 $$$4$$$ 节点来使区域的并集与 $$$[1,3] \times [1,3]$$$ 完全相同:
- 叶子节点占$$$[1,2] \times [1,2]$$$;
- 叶子节点占$$$[1,2] \times [2,3]$$$;
- 叶子节点占$$$[2,3] \times [1,2]$$$;
- 叶节点占 $$$[2,3] \times [2,3]$$$。
可以证明,节点数少于 $$$4$$$ 的区域的并集不可能与 $$$[1,3] \times [1,3]$$$ 完全相同。因此,答案是$$$4$$$。
在第四个测试用例中,给定区域为 $$$[0,2] \times [1,5]$$$。通过选择以下 $$$5$$$ 节点,您可以使区域的并集与 $$$[0,2] \times [1,5]$$$ 完全相同:
- 叶子节点占$$$[0,1] \times [1,2]$$$;
- 叶子节点占$$$[1,2] \times [1,2]$$$;
- A 非叶 节点占$$$[0,2]\times [2,4]$$$;
- 叶子节点占$$$[0,1] \times [4,5]$$$;
- 叶节点占 $$$[1,2] \times [4,5]$$$。
可以证明,节点数少于 $$$5$$$ 的区域的并集不可能与 $$$[0,2] \times [1,5]$$$ 完全相同。因此,答案是$$$5$$$。