Go Back

##### Nishant's Diwali Puzzle (100)

Description

The Festival of Lights is here. Nishant wants to buy a new Lantern this Diwali. He visits your shop and finds that the lanterns are arranged arbitrarily. You inform Nishant that the cost **C** of the lanterns are *directly proportional* to their size. Nishant likes puzzles and wants you to solve one.

Nishant lists the cost of all the lanterns. He finds that the list has some consecutive sub-sequences of Even Numbers. He wants you to make a new list consisting of the maximum number from each consecutive sub-sequence of even numbers. He expects that you find the minimum number from this new list.

If you answer it correctly, Nishant will buy the lantern of that cost from your shop. If there are no even sub-sequences, Nishant expects **-1** as the answer.

Solve Nishantâ€™s puzzle to find the cost of the lantern he will buy.

Input

The first line of the input is an integer **T** denoting the number of test cases.

The next **T** lines contain a sequence of space-separated integers denoting the cost **C** of lanterns.

Output

Output the cost of the lantern Nishant will buy, in a single line.

Constraints

1<=**T**<=100

1<=**C**<=10^5

Example

Copy Input

**Input**:

3

3 4 6 5 12 6 18 14 9 11 10

2 4 6 8 1 3 5 8 10 7 9 11 12 14 16

1 3 5 7 9**Output**:

6

8

-1

Explanation

**Case 1**:

The first even sub-sequence is {4, 6}. The maximum value in this sequence is 6. The next even sub-sequence is {12, 6, 18, 14}. The maximum value in this sequence is 18. The next even sub- sequence is {10}. The maximum value in this sequence is 10. Now, the new list of maximum values from each even sub-sequence is {6, 18, 10}. The minimum value in this new list is 6.**Case 2**:

The first even sub-sequence is {2, 4, 6, 8}. The maximum value in this sequence is 8. The next even sub-sequence is {8, 10}. The maximum value in this sequence is 10. The next even sub-sequence is {12, 14, 16}. The maximum value in this sequence is 16. Now, the new list of maximum values from each even sub-sequence is {8, 10, 16}. The minimum value in this new list is 8.**Case 3**:

As there are no even terms in the sequence, we output -1

Tips and Tricks for Python: Visit Here

Tips and Tricks for C++: Visit Here

Tips and Tricks for Java: Visit Here