【题目描述】

小C 养了一些很可爱的兔子。
有一天，小 C 突然发现兔子们都是严格按照伟大的数学家斐波那契提出的模型来进行繁衍：一对兔子从出生后第二个月起，每个月刚开始的时候都会产下一对小兔子。我们假定，在整个过程中兔子不会出现任何意外。
小 C 把兔子按出生顺序，把兔子们从 1 开始标号，并且小 C 的兔子都是 1 号兔子和 1号兔子的后代。如果某两对兔子是同时出生的，那么小 C 会将父母标号更小的一对优先标号。
如果我们把这种关系用图画下来，前六个月大概就是这样的：

其中，一个箭头 A →B 表示A 是 B 的祖先，相同的颜色表示同一个月出生的兔子。 为了更细致地了解兔子们是如何繁衍的，小C 找来了一些兔子，并且向你提出了 m 个问题：她想知道关于每两对兔子 Ai 和 Bi ，他们的最近公共祖先是谁。你能帮帮小C 吗？

一对兔子的祖先是这对兔子以及他们父母（如果有的话）的祖先，而最近公共祖先是指两对兔子所共有的祖先中，离他们的距离之和最近的一对兔子。比如，5和7的最近公共祖先是2，1 和2的最近公共祖先是 1，6和6 的最近公共祖先是6。

【输入格式】

从文件fibonacci.in中读入数据。
输入第一行，包含一个正整数 m。
输入接下来 m 行，每行包含2 个正整数，表示 Ai 和 Bi 。

【输出格式】

输出到文件fibonacci.out中。
输入一共 m 行，每行一个正整数，依次表示你对问题的答案。

【样例1 输入】

5 
1 1 
2 3 
5 7 
7 13 
4 12 

【样例1输出】

1 
1 
2 
2 
4 

【样例2】

见选手目录下的fibonacci/fibonacci2.in 与 fibonacci/fibonacci2.ans。

【数据范围与约定】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。
每个测试点的数据规模及特点如下表：