Boxes#10454

Boxes

1 second

256 megabytes

Medium

There are $n$ boxes in a row, each colored either white or black. The boxes are numbered from left to right from $1$ to $n$ . Barysh gets annoyed when he sees a white box immediately following a black one. Therefore, he asks you to swap the boxes in every consecutive pair ${black, white}$ \{\text{black}, \text{white}\}.

In one pass, first find all pairs of consecutive boxes ${black, white}$ \{\text{black}, \text{white}\}, and then swap the boxes in each found pair. After one pass, there may still be consecutive ${black, white}$ \{\text{black}, \text{white}\} pairs in the row. In that case, repeat the process.

How many passes do you need to ensure that no consecutive pair ${black, white}$ \{\text{black}, \text{white}\} remains in the row?

Input

The first line contains the integer $t$ ( $1 \leq t \leq 100$ 1 \le t \le 100) — the number of test cases.

For each test case, the first line contains an integer $n$ ( $1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4) — the number of boxes. The second line contains $n$ integers $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n.

Each $p_{i}$ p_i describes the color of the $i$ -th box: $p_{i} = 1$ p_i = 1 means the box is black, and $p_{i} = 0$ p_i = 0 means the box is white.

Output

For each test case, print on a separate line a single integer — the number of passes required.

Examples

Example 1

Note

Constraints

$1 \leq t \leq 100$ 1 \le t \le 100
$1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4
$p_{i} \in {0, 1}$ p_i \in \{0, 1\}

Scoring

This problem consists of $2$ subtasks:

Subtask	Restrictions	Points
0	Sample	0
1	$n \leq 100$ n \le 100	15
2	No additional restrictions	85