Zebel’s Game

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Zebel has put some pegs into his study desk and drew a non-self-intersecting path on the desk between two specific points s and d. He is now curious to know that if the path was created by an elastic band and its endpoints were fixed, what would happen to the elastic band after releasing it. To mathematically answer this question, he assigns a unique id (a positive integer) to each peg and draws a vertical line passing through the peg. Then he creates the path sequence (PS) as follows: he puts his pen at point s and starts moving it along the path toward d. Whenever he reaches a vertical line drawn from a peg, say the peg with id n, if the pen is above the peg he appends n to the sequence, and –n otherwise. For example, for the figure below, the PS he writes will be 1 2 3 4 4 3 3 3 -2 -1. Note that no two pegs are placed in the same vertical line.

His experiment shows if the path is created by an elastic band, every two equal adjacent numbers in the PS are omitted and this continues until a canonical sequence (CS) is obtained where no two adjacent numbers are equal. For the example figure, the canonical sequence will be 1 2 -2 -1.

 

As the next experiment, he wants to know removing which peg from the table creates a CS with the minimum length (the length of a sequence is the number of items in the sequence). Your task is to find this peg.

Input

The first line of the input contains a single integer t (1 <= t <= 15), the number of test cases, followed by the input data for each test case. Each test case consists of one line containing a path sequence (PS) as a sequence of integer numbers. Each line contains at most 10⁴ numbers and the numbers are within range [-10⁶, 10⁶].

Output

For each test case the id of a peg whose removal creates a CS with the minimum length should be printed in one line in the output. If such a peg is not unique, print the peg with the minimum id.

Sample Input

1
1 2 3 4 4 3 3 3 -2 -1

Sample Output

1

Submit

Source: 9th Iran Nationwide Internet Contest