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 =bt_1~, ~t_2~, ..., ~t_k~, ~(3 \leq k \leq 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_1~, ~t_2~,..., ~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.

Sample Input

2
1 2 1 2
1 2 1 2 1 2

Sample Output

2
4