In order to discover all the planets of the solar system, we want to develop techniques to travel safely through an asteroid belt between Mars and Jupiter.

We plan to drop automatic-signaling devices into large asteroids of the belt, which will act as space beacons to guide the ships.

They will assist autopilots to track the location of the ships to adjust the orbit. Each signal sent by each beacon contains a sequence of pulses, and is characterized by a sequence T :

T = t₁, t₂,..., t_k,(3 ≤ k ≤ 18)

Where t_i is the duration of i -th pulse (t_i is integer and is in the range of 1..9).

In order to simplify the technical checking process and to increase the signal recognition ability, the sequence T of each beacon is designed with the following criteria:

With 1 < i < k , either:

t_i-1 < t_i, t_i > t_i+1 for i mod 2 = 0

t_i-1 > t_i, t_i < t_i+1 for i mod 2 = 1

or

t_i-1 > t_i, t_i < t_i+1 for i mod 2 = 0

t_i-1 < t_i, t_i > t_i+1 for i mod 2 = 1

All possible T sequences are sorted in lexicographic order and labeled by consecutive integers starting with 1. The label of the sequence T of each beacon is used as the identifier of the beacon.

Given the sequence T of a beacon, your task is to write a program to find the identifier of that beacon.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20.

The following lines describe the data sets.

For each data set, there is only one single line containing k integers t₁, t₂,..., t_k separated by space describing the T sequence of a beacon.

Output

For each test case, write in one line the ID of the beacon with the given T sequence.