题目描述

你带领着一队埋伏兵，对敌军发起偷袭。在战斗开始前，你需要尽快让所有的士兵靠近前线，以发动进攻。

一共有$n$个埋伏点，按照距离前线由近到远的顺序依次编号为$1,2,…,n$每个埋伏点最多埋伏一位士兵。现在所有士兵分散在这$n$个埋伏点间，具体地，我们用$n$个值为$0$或$1$的整数$a_i(i=1,2,…,n)$ 描述当前的情况，如果 $a_i=1$，表示埋伏点$i$有士兵，如果$a_i=0$，表示埋伏点$i$为空。

由于敌军已在侦查我方情况，你需要在保证安全的情况下尽快让所有士兵向前线移动。因此，你打算让士兵这样行动：每秒钟，所有前方为空埋伏点的士兵同时向前移动一步，其余士兵不动，即对于所有满足 $2≤i≤n$，$a_{i−1}=0$，$a_i=1$的$i$，令 $a_i←0$，$a_{i-1}←1$ ，其余的 $a_i$ 不变。

当所有的士兵前方没有空埋伏点，即对任意 $2≤i≤n$ 且 $a_i=1$ 均有 $a_{i-1}=1$ 时，认为所有士兵已到达前线。现在你需要预测所有士兵到达前线的最短时间。

输入格式

输入的第一行包含一个正整数$T$，表示数据组数。之后依次输入$T$组数据。

对于每组数据，第一行包含一个正整数$n$，表示埋伏点个数。

第二行包含$n$个由空格分隔的整数$a_1,a_2,....,a_n$，其中 $a_i∈${$0,1$}，表示每个埋伏点是否有士兵。

输出格式

对每组数据依次输出答案。

输出的每行包含一个整数，表示对应的输入数据中，所有士兵到达前线需要多少秒。

样例

3
10
0 1 1 1 0 1 1 0 1 1
5
0 1 0 1 1
1000
0 0 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1

7
3
699

我们用$[a_1,a_2,…,a_n]$描述一个时刻的局面。

对于第1组数据，初始局面为$[0,1,1,1,0,1,1,0,1,1]$

经过1秒后:$[1,0,1,1,1,0,1,1,0,1]$

经过2秒后:$[1,1,0,1,1,1,0,1,1,0]$

经过3秒后:$[1,1,1,0,1,1,1,0,1,0]$

经过4秒后:$[1,1,1,1,0,1,1,1,0,0]$

经过5秒后:$[1,1,1,1,1,0,1,1,0,0]$

经过6秒后:$[1,1,1,1,1,1,0,1,0,0]$

经过7秒后:$[1,1,1,1,1,1,1,0,0,0]$

因此所有士兵到达前线需要7秒。

对于第2组数据，初始局面为$[0,1,0,1,1]$。

经过1秒后:$[1,0,1,0,1]$

经过2秒后:$[1,1,0,1,0]$

经过3秒后:$[1,1,1,0,0]$

因此所有士兵到达前线需要3秒。

Limitation

见pdf