Lambda-plant#2636

Lambda-plant

1 second
256 megabytes
Medium

Recently, a meteorite landed in front of Losyash's house. The next morning, Losyash discovered a mysterious new plant growing in his flowerbed. As days passed, the plant grew, and one night Losyash noticed that some of its parts were glowing.

The plant consists of many spherical bulbs, some of which are connected by stems. After carefully analyzing the plant, Losyash determined that the bulbs are connected in the following way: if we assign a number to each bulb, then bulb number , which is the root of the plant, is connected to bulb number ; bulb is connected to bulbs , , and . For any bulb with a number greater than , if is odd, it is connected to i-1; if is even, it is connected to i-2, i+1, and i+2.

While studying the glowing patterns, Losyash discovered that if he touches bulbs numbered and , the bulb with the smallest number on the shortest path between the -th and -th bulbs begins to glow.

Since Losyash's plant is not very large yet, he asks you to calculate the number of the bulb that will start to glow when he touches bulbs and .

Input

The first line contains an integer (1 \leq n \leq 100) — the number of pairs of bulbs Losyash is interested in. Each of the next lines contains two integers v_i and u_i (1 \leq u_i, v_i \leq 10^9, u_i \ne v_i) — the numbers of the -th pair of bulbs.

Output

For each pair, on a separate line, output the number of the bulb that will start to glow when bulbs u_i and v_i are touched.

Examples

Example 1

Loading
Loading