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.

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.

Grid Puzzle

Examples