eolymp
Competitions

2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8

Boxes

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

  • 1t100
  • 1n104
  • pi = 0, 1

Subtasks

This problem consists of 2 subtasks:

SubtaskRestrictionsPoints
0Example0 points
1n10015 points
2No additional restrictions85 points
Time limit 1 second
Memory limit 256 MiB
Input example #1
3
5
1 1 0 1 0
3
1 0 1
4
1 0 1 0
Output example #1
3
1
2
Source 2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8