SP5541 SEQUOIA - Sequoiadendron

「Sequoiadendron giganteum（巨型红杉、塞拉红杉或惠灵顿树）是唯一的红杉属物种，属于三种称为红杉的针叶树之一。这三种树分别被归类在柏科的红杉亚科中，其他两种是 Sequoia sempervirens（海岸红杉）和 Metasequoia glyptostroboides（水杉）。通常所指的“红杉”一般是指 Sequoiadendron，它只在美国加利福尼亚州内华达山脉西坡的若干林地中自然生长。」——摘自维基百科。 我们重新定义这种树以适应题目的需要： 假设这棵树是无限大的，并且从根节点 0 开始。树的定义递归如下： 假定$x$是某个子树的根节点。对于所有$i \in [0, \lg(x - \text{dad}(x))]$，我们规定$x$的子节点是形如$2^i + x$的节点，其中$\text{dad}(x)$表示$x$的父节点索引。节点 0 拥有无限多个子节点。奇数节点没有子节点。 你将得到多个查询，每个查询包括两个整数 $A$ 和 $B$。你的任务是输出 $A$ 和 $B$ 的最近公共祖先的索引。最近公共祖先定义为在从 $A$ 到 0 和从 $B$ 到 0 的路径中与 $A$ 和 $B$ 最近的公共节点。

第一行为整数 $N$，表示总共有多少个查询。（$1 \le N \le 100000$） 接下来的 $N$ 行中每行包含一对整数 $A$ 和 $B$。（$0 \le A, B \le 10^{18}$）

请输出 $N$ 行，其中第 $i$ 行为第 $i$ 个查询的答案。 **本翻译由 AI 自动生成**