C. Guess the Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A certain natural number is hidden. Three statements have been made about it:

  1. This number is greater than $$$A$$$ and less than $$$B$$$;
  2. This number is not greater than $$$C$$$ or not less than $$$D$$$;
  3. This is an even number, and it is greater than $$$E$$$.
All three statements are false.

You need to determine what is the smallest natural number that could have been hidden (or if such a number does not exist). You need to find the answer for several test cases.

Input

The first line of the input contains an integer $$$T$$$ — the number of test cases ($$$1 \le T \le 1000$$$).

In each of the following $$$T$$$ lines, five integers $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$, $$$E$$$ are given, separated by spaces ($$$0 \le A, B, C, D, E \le 10^9$$$).

Output

For each test case, output the smallest natural number that could have been hidden. If such numbers do not exist, output -1.

Scoring

Solutions that work for $$$T=1$$$ and $$$A, B, C, D, E \le 100$$$ will be scored 40 points.

Example
Input
2
5 8 4 10 3
7 8 7 3 9
Output
5
-1
Note

Note for participants writing in Python. You can read 5 numbers entered with spaces like this:

a, b, c, d, e = map(int, input().split())