Raising the Glasses

Team Red and Team Blue play a drinking game, where teams alternate turns. Team Red chooses the number of glasses N from an interval [a..b] and also plays the first turn.

After N is chosen, glasses numbered from 1 to N are lined up orderly in a single line with glass #1 at the leftmost and glass #N at the rightmost.

In each turn, the captain of the team next in line, selects exactly one glass among the existing ones. The selected glass and its immediate adjacent glasses to the left and right (if any) are picked up and taken away by the team. The team who cannot make any move loses the game. In other words, the team who makes the last move and takes away the last glass or glasses wins.

Observe that there are values for N for which the victory of Team Red can be guaranteed. As in these cases there exists a sure-win strategy for Team Red, we call these winning positions.

For example, N = 1, N = 2, or N = 3 are such winning positions, as Team Red removes all glasses in one move, winning the game. For N = 4, there's no sure-win strategy, whatever Team Red moves first, will result in one or two adjacent glasses remaining on the table, which will be cleared by Team Blue in the next turn. N = 5 is again a winning position for Team Red, the winning strategy consists in picking first glass #3. This will leave 2 non-adjacent glasses, namely glass #1 and glass #5 on the table. Only one of them can be cleared by Team Blue in the next turn, leaving one behind for Team Red to secure the victory.

Your job is to help Team Red. Given the lower bound a and the upper bound b for the number of glasses, you have to determine the smallest number of glasses N (a ≤ N ≤ b) that is winning position for Team Red, or return –1 if no such winning position exists in the [a..b] interval.

Input Specification

The first line of the input contains an integer T (T ≤ 10 000) denoting the number of cases. Each case contains two integers a and b (1 ≤ a ≤ b ≤ 1 000 000 000) in a line, denoting the lower bound and upper bound from which the smallest winning position N must be chosen if it exist.

Output Specification

For each test case, output in a line the smallest integer N that is winning position for the respective input, or –1 if there is no sure-win strategy.

Sample Input

1. 5
2. 1 3
3. 2 5
4. 3 3
5. 4 4
6. 4 5

download as text file

Output for Sample Input

1. 1
2. 2
3. 3
4. -1
5. 5

download as text file