Dragon Head Severance

You are given a dragon with N heads. Each head has a power level, though the power levels are not used in the decision making. In one operation you can sever either a single head or two adjacent heads. Your goal is to determine the minimum number of operations required to sever all the heads of the dragon.

Mathematically, the answer for a dragon with N heads is given by:

$$\lceil \frac{N}{2} \rceil = \frac{N+1}{2}\ (integer\ division)$$

You will be given multiple test cases.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer T denoting the number of test cases.
2. For each test case:
• The first line contains an integer N denoting the number of heads.
• The second line contains N space-separated integers representing the power levels of each head.

outputFormat

For each test case, print the minimum number of operations needed to sever all the dragon's heads. Each answer should be printed on a new line to stdout.

## sample

3
5
1 2 3 4 5
4
4 4 4 4
3
10 1 10

3
2
2

</p>