Maximizing Non-Adjacent Tree Cuts

You are given a row of trees. Your task is to determine the maximum number of trees that can be cut down such that no two cut trees are adjacent. Mathematically, this problem can be expressed as follows:

[ \text{answer} = \left\lceil \frac{n}{2} \right\rceil ]

where ( n ) is the total number of trees. Although the heights of the trees are provided as input, they do not affect the outcome.

inputFormat

The first line of input contains an integer ( T ) representing the number of test cases. Each test case begins with a line containing an integer ( n ) (the number of trees). If ( n > 0 ), the next line contains ( n ) space-separated integers denoting the heights of the trees.

outputFormat

For each test case, print a single integer on a new line representing the maximum number of trees that can be cut down with the restriction that no two cut trees are adjacent.## sample

8
5
1 2 3 4 5
6
3 4 5 6 7 8
1
1000000000
3
200000000 2 500000000
2
1 2
4
1 2 3 4
0
7
2 3 4 5 6 7 8

3
3
1
2
1
2
0
4