Lambda-plant

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 went by, the plant grew, and one night Losyash noticed that some parts of it were glowing.

The plant is made up of numerous spherical bulbs, some of which are connected by stems. After examining the plant, Losyash found that the bulbs are connected in a specific pattern: if each bulb is assigned a number, then bulb number one, which is the root of the plant, is connected to bulb number two. Bulb two is connected to bulbs one, three, and four. For any bulb (i) with a number greater than two, it is connected to (i-1) if (i) is odd, or to (i-2), (i+1), and (i+2) if (i) is even.

When Losyash began studying the glowing patterns, he discovered that if he touched bulbs numbered (u) and (v), the bulb with the smallest number on the shortest path between the (u)-th and (v)-th bulbs would start to glow.

Since Losyash's plant is not very large yet, he asked you to determine the number of the bulb that will start to glow if he touches bulbs (u) and (v).

Input

The first line of the input contains a single integer (n) ((1 $\le$ n $\le$ 100)) - the number of pairs of bulbs that interest Losyash. The next (n) lines each contain two numbers (v_i) and (u_i) ((1 $\le$ u_i, v_i $\le$ 10^9), (u_i $\ne$ v_i)) - representing the numbers of the (i)-th pair of bulbs.

Output

For each pair, print on a new line the number of the bulb that will start to glow if you touch bulbs (u_i) and (v_i).

Examples