D. Grid Puzzle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$.

There is an $$$n \times n$$$ grid. In the $$$i$$$-th row, the first $$$a_i$$$ cells are black and the other cells are white. In other words, note $$$(i,j)$$$ as the cell in the $$$i$$$-th row and $$$j$$$-th column, cells $$$(i,1), (i,2), \ldots, (i,a_i)$$$ are black, and cells $$$(i,a_i+1), \ldots, (i,n)$$$ are white.

You can do the following operations any number of times in any order:

  • Dye a $$$2 \times 2$$$ subgrid white;
  • Dye a whole row white. Note you can not dye a whole column white.

Find the minimum number of operations to dye all cells white.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the size of the array $$$a$$$.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

It's guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum number of operations to dye all cells white.

Example
Input
10
1
0
4
2 4 4 2
4
3 2 1 0
3
0 3 0
3
0 1 3
3
3 1 0
4
3 1 0 3
4
0 2 2 2
6
1 3 4 2 0 4
8
2 2 5 2 3 4 2 4
Output
0
3
2
1
2
2
3
2
4
6
Note

In the first test case, you don't need to do any operation.

In the second test case, you can do:

  • Dye $$$(1,1), (1,2), (2,1)$$$, and $$$(2,2)$$$ white;
  • Dye $$$(2,3), (2,4), (3,3)$$$, and $$$(3,4)$$$ white;
  • Dye $$$(3,1), (3,2), (4,1)$$$, and $$$(4,2)$$$ white.

It can be proven $$$3$$$ is the minimum number of operations.

In the third test case, you can do:

  • Dye the first row white;
  • Dye $$$(2,1), (2,2), (3,1)$$$, and $$$(3,2)$$$ white.

It can be proven $$$2$$$ is the minimum number of operations.