Fibonacci Rabbit Lineage LCA

Little C keeps some adorable rabbits. One day, she discovered that the rabbits reproduce strictly according to the model proposed by the great mathematician Fibonacci. The reproduction rule is as follows: A pair of rabbits, starting from the month immediately after their birth month (i.e. when they become at least 2 months old), produces one new pair at the beginning of each month. We assume that no rabbit pair ever dies.

All rabbit pairs are numbered by their birth order starting from 1. The initial pair is numbered 1, and every new pair is a descendant of pair 1. If several pairs are born in the same month, the order is determined by the parent's number (the pair with the smaller parent's number gets the lower new number).

We can imagine the rabbit family as a tree. An arrow from A to B (i.e. \(A \to B\)) indicates that A is an ancestor of B (here, an ancestor of a pair is the pair itself and all the ancestors of its parent, if any). The lowest common ancestor (LCA) of two pairs is defined as the common ancestor for which the sum of distances (in terms of the number of edges) from the two pairs is minimized.

For example:

• The LCA of pairs 5 and 7 is 2.
• The LCA of pairs 1 and 6 is 1.
• The LCA of pair 6 with itself is 6.

You are given m queries. Each query provides two rabbit pair numbers \(a_i\) and \(b_i\). For each query, determine the lowest common ancestor of the two given pairs.

Note: You may assume that the input queries are such that the maximum rabbit number required is small enough to simulate the reproduction process month by month.

inputFormat

The first line contains an integer \(m\) \( (m \ge 1) \) representing the number of queries. Each of the following \(m\) lines contains two integers \(a_i\) and \(b_i\) (\(a_i, b_i \ge 1\)), separated by a space, indicating the numbers of two rabbit pairs.

outputFormat

For each query, output a single line containing a single integer, which is the number of the lowest common ancestor of the two given rabbit pairs.

sample

3
5 7
1 6
6 6

2
1
6