P3938 斐波那契

大样例可在页面底部「附件」中下载。

小 C 养了一些很可爱的兔子。有一天，小 C 突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行繁衍：一对兔子从出生后第二个月起，每个月刚开始的时候都会产下一对小兔子。我们假定，在整个过程中兔子不会出现任何意外。 小 C 把兔子按出生顺序，把兔子们从 1 开始标号，并且小 C 的兔子都是 1 号兔子和 1 号兔子的后代。如果某两对兔子是同时出生的，那么小 C 会将父母标号更小的一对优先标号。 如果我们把这种关系用图画下来，前六个月大概就是这样的：  其中，一个箭头 $A \to B$ 表示 $A$ 是 $B$ 的祖先，相同的颜色表示同一个月出生的兔子。 为了更细致地了解兔子们是如何繁衍的，小 C 找来了一些兔子，并且向你提出了 $m$ 个问题：她想知道关于每两对兔子 $a_i$ 和 $b_i$，他们的最近公共祖先是谁。你能帮帮小 C 吗？ 一对兔子的祖先是这对兔子以及他们父母（如果有的话）的祖先，而最近公共祖先是指两对兔子所共有的祖先中，离他们的距离之和最近的一对兔子。比如，$5$ 和 $7$ 的最近公共祖先是 $2,1$ 和 $2$ 的最近公共祖先是 $1,6$ 和 $6$ 的最近公共祖先是 $6$。

输入第一行，包含一个正整数 $m$。输入接下来 $m$ 行，每行包含 $2$ 个正整数，表示 $a_i$ 和 $b_i$。

输出一共 $m$ 行，每行一个正整数，依次表示你对问题的答案。

【数据范围与约定】 子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。每个测试点的数据规模及特点如下表： ::cute-table{tuack} | 测试点 | $m$ | $a_i,b_i$ | 特殊性质 $1$ | 特殊性质 $2$ | |:-:|:-:|:-:|:-:|:-:| | $1$ | $11$ | $\le 15$ | $\checkmark$ | $\checkmark$ | | $2$ | $12$ | ^ | $\times$ | $\times$ | | $3$ | $13$ | $\le1000$ | $\checkmark$ | ^ | | $4$ | $14$ | ^ | $\times$ | ^ | | $5$ | $1005$ | $\le 10^6$ | $\checkmark$ | ^ | | $6$ | $1006$ | ^ | $\times$ | $\checkmark$ | | $7$ | $1007$ | ^ | ^ | $\times$ | | $8$ | $300008$ | $\le10^{12}$ | $\checkmark$ | ^ | | $9$ | $300009$ | ^ | $\times$ | $\checkmark$ | | $10$ | $300010$ | ^ | ^ | $\times$ | 特殊性质 $1$：保证 $a_i$, $b_i$ 均为某一个月出生的兔子中标号最大的一对兔子。例如，对于前六个月，标号最大的兔子分别是 $1, 2, 3, 5, 8, 13$。 特殊性质 $2$：保证 $|a_i-b_i|\le 1$。