Background

At last, the warrior defeats the Demon King and traps him in a room with no way out.

The Demon King can move freely in the dark, so the warrior can only find him and destroy him completely by turning on all the lights in the room.

Problem Description

There are $n$ lights in the room. The initial state is represented by $a_1 \dots a_n$, where $\tt 0$ means the light is initially off, and $\tt 1$ means the light is initially on.

Starting from the morning of day 1, the Demon King and the warrior take turns to act:

• Every morning, the Demon King may choose two consecutive lights and set both of their states to $\tt 0$.
• Every night, the warrior may choose up to three arbitrary lights and set all of their states to $\tt 1$.

For each action, the states of the chosen lights before being set can be anything.

Assume both sides use optimal strategies and will not make any move that is disadvantageous to themselves. The warrior wants to know the minimum number of days (that is, the minimum number of his operations) needed to set all lights to $\tt 1$—only then can he catch the hateful Demon King and marry the beautiful princess.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains an integer $n$, the total number of lights.
• The second line contains $n$ numbers, in order, representing $a_1 \dots a_n$.

Output Format

For each test case, output one integer per line, the minimum number of days needed for the warrior to catch the Demon King.

In particular, if the warrior does not need to do any operation, output $0$.

4
5
1 0 1 0 1
5
1 0 0 1 1
9
0 0 0 0 0 0 0 0 0
13
0 1 0 0 1 0 1 0 0 0 0 0 0

1
2
5
8

Hint

Sample Explanation 1

• On the morning of day 1, the Demon King turns off lights $1{,}2$.
• On the night of day 1, the warrior turns on lights $1{,}2{,}4$.

Sample Explanation 2

• On the morning of day 1, the Demon King turns off lights $4{,}5$.
• On the night of day 1, the warrior turns on lights $2{,}3{,}4$.
• On the morning of day 2, the Demon King turns off lights $1{,}2$.
• On the night of day 2, the warrior turns on lights $1{,}2{,}5$.

Constraints

This problem uses bundled testdata.

• Subtask 0 (10 points): $n \leq 10$, $T \leq 2046$.
• Subtask 1 (30 points): $n \leq 2000$.
• Subtask 2 (10 points): Initially, all lights are off.
• Subtask 3 (20 points): The testdata is randomly generated.
• Subtask 4 (30 points): No special restrictions.

For all testdata, $1 \leq T \leq 10^6$, $1 \leq n \leq 10^6$, $1 \leq \sum n \leq 3 \times 10^6$.

Translated by ChatGPT 5