There are n white and black boxes in one row. The boxes are numbered from left to right from 1 to n. Looking through the boxes Barysh gets annoyed when he sees a white box right after the black one. Therefore, he asks you to swap the boxes in all consecutive pairs {black, white}.

In one pass, you first define all pairs of boxes {black, white}, and then swap boxes in all found pairs. After one pass, there may still be consecutive {black, white} pairs in the row. In this case, it is necessary to repeat the described process.

How many passes do you need to make so that no consecutive pair {black, white} remains in the row?

Input

The first line contains the number t - the number of tests.

In each of the following t tests, the first line contains the number n, and the second line contains n numbers pi.

pi indicates the color of the i - th box: pi = 1 black, and pi = 0 white.

Output

For each of the test cases, print on a separate line one number - the number of passes.

Restrictions

• 1 ≤ t ≤ 100
• 1 ≤ n ≤ 104
• pi = 0, 1

Subtasks

This problem consists of 2 subtasks: