Enegy Transporter

At a certain research institute, I was developing a medium for energy transfer. This medium has a polymer structure consisting of a special substance as shown in Fig. 3.

Structure of energy transfer medium.

(-α-Ea-β-) n Figure 3: Structure of energy transfer medium.

The part shown by Ea in the figure is the Energy Accumulator, which is the most characteristic part of this medium. This Ea group can take various energy states discretized with a width of 1 kJ. Exciting a certain Ea group has the effect of transferring all the energy stored in the adjacent Ea group bonded to the α side of the Ea group to the adjacent Ea group bonded to the β side. An exothermic reaction is triggered (Fig. 4). During this reaction, the energy of the excited Ea group is consumed by 1 kJ. It should be noted that the excitation reaction does not occur for the Ea groups located at both ends of the polymer and the Ea groups whose energy state is 0 kJ, and that the Ea groups can store a sufficiently large amount of energy. Are known.

Reaction when the central Ea group is excited.

Figure 4: Reaction when the central Ea group is excited.

We were thinking of using this property to enable energy transfer, but researchers realized that the order in which each Ea group was excited was important for efficient energy transfer. ..

Fortunately, the order and number of excitations can be controlled arbitrarily, but they do not know the optimum excitation procedure. Therefore, as a stepping stone to their ideas, I would like you to calculate the maximum amount of energy that can be stored in the rightmost Ea group (the Ea group closest to the β end) with respect to the energy distribution in the initial state.

Input

The input consists of multiple datasets and is given in the following format.

N C1 C2 ... CN

The integer N (0 <N ≤ 60) at the beginning of the input is the number of datasets in question, and the information Ck for each dataset is given over the last 2N lines.

Each dataset Ck is given over two lines in the following format.

L E1 E2 ... EL

L is the length of the Ea chain of the medium handled by each data set, which means that the number of Ea groups given here are bonded in series. The L integer Ek in the next row is the amount of energy initially stored in the kth Ea chain counting from the left when the α end of the Ea chain of length L is placed at the left end, in kJ units. It is shown.

Here, it is guaranteed that 0 ≤ Ek ≤ 4, 1 ≤ L ≤ 80.

Output

For each data set, describe the maximum energy that can reach the rightmost Ea chain under a given situation in kJ units, and describe only the integer value on one line.

Example

Input

7 1 2 2 1 2 3 4 1 4 3 4 0 4 5 4 1 4 0 4 5 4 1 4 1 4 5 4 2 4 0 4

Output

2 2 8 4 7 12 11

inputFormat

Input

The input consists of multiple datasets and is given in the following format.

N C1 C2 ... CN

The integer N (0 <N ≤ 60) at the beginning of the input is the number of datasets in question, and the information Ck for each dataset is given over the last 2N lines.

Each dataset Ck is given over two lines in the following format.

L E1 E2 ... EL

L is the length of the Ea chain of the medium handled by each data set, which means that the number of Ea groups given here are bonded in series. The L integer Ek in the next row is the amount of energy initially stored in the kth Ea chain counting from the left when the α end of the Ea chain of length L is placed at the left end, in kJ units. It is shown.

Here, it is guaranteed that 0 ≤ Ek ≤ 4, 1 ≤ L ≤ 80.

outputFormat

Output

For each data set, describe the maximum energy that can reach the rightmost Ea chain under a given situation in kJ units, and describe only the integer value on one line.

Example

Input

7 1 2 2 1 2 3 4 1 4 3 4 0 4 5 4 1 4 0 4 5 4 1 4 1 4 5 4 2 4 0 4

Output

2 2 8 4 7 12 11

样例

7
1
2
2
1 2
3
4 1 4
3
4 0 4
5
4 1 4 0 4
5
4 1 4 1 4
5
4 2 4 0 4

2
2
8
4
7
12
11

</p>