Description

Xiao C (pinyin) keeps some very cute rabbits. One day, Xiao C suddenly discovered that the rabbits reproduce strictly according to the model proposed by the great mathematician Fibonacci: starting from the second month after birth, at the beginning of each month a pair of rabbits gives birth to one new pair. We assume that no accidents occur during the entire process.

Xiao C numbers the rabbit pairs in order of birth starting from 1, and all the rabbits are the No. 1 pair and its descendants. If two pairs of rabbits are born at the same time, Xiao C assigns numbers first to the pair whose parents have smaller labels.

If we draw this relationship as a graph, the first six months look roughly like this:

Here, an arrow $A \to B$ means that $A$ is an ancestor of $B$, and the same color indicates that the pairs were born in the same month.

To understand the reproduction in more detail, Xiao C picked some pairs of rabbits and asked you $m$ questions: for each two pairs of rabbits $a_i$ and $b_i$, she wants to know their lowest common ancestor. Can you help Xiao C?

An ancestor of a pair is the pair itself and the ancestors of its parents (if any). The lowest common ancestor (LCA) is the common ancestor of the two pairs that minimizes the sum of distances to them. For example, the LCA of $5$ and $7$ is $2$, the LCA of $1$ and $2$ is $1$, and the LCA of $6$ and $6$ is $6$.

Description

Input Format

The first line contains a positive integer $m$. Each of the next $m$ lines contains $2$ positive integers, representing $a_i$ and $b_i$.

Output Format

Output $m$ lines. Each line contains one positive integer, in order, representing your answer to the corresponding query.

5 
1 1 
2 3 
5 7 
7 13 
4 12

1 
1 
2 
2 
4 

Hint

Constraints and Conventions. Subtasks provide characteristics of some testdata. If you encounter difficulties, you may try to solve only part of the testdata. The scale and characteristics of each test point are shown in the table below:

Special property 1: It is guaranteed that $a_i$ and $b_i$ are both the pair with the largest label among those born in some month. For example, for the first six months, the largest labels are $1, 2, 3, 5, 8, 13$.

Special property 2: It is guaranteed that $|a_i-b_i|\le 1$.

Translated by ChatGPT 5