You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知, 掉入沼泽地可不是一件好玩的事情~

题目描述

你在森林的一条小路上行走, 每个点可以看做一个坐标点, 每个位置可以是陆地, 也可以是沼泽, 你不能掉入沼泽, 否则会开席. 你可以走到相邻的陆地上, 不需要花费体力, 如果你想跳跃沼泽, 比如从 $x$ 位置跳跃到 $x+d$ 位置, 你需要花费 $d$ 的体力. 不过不幸的是, 你最多只能跳跃一次.

现在你想知道你需要花费最少多少体力可以穿越这条危险的小路.

数据格式

输入格式

第一行输入一个整数 $t$, 表示有 $t$ 组数据.

接下来每组数据, 第一行输入一个整数 $n$, 表示这条路的长度, 接下来 $n$ 个整数 $0$ 或 $1$, 用 $0$ 表示沼泽, $1$ 表示陆地, 确保 $1, n$ 位置为陆地.

输出格式

输出 $t$ 行, 每行一个整数表示最少花费多少体力.

样例

3
5
1 1 1 1 1
6
1 0 1 0 0 1
8
1 1 1 0 0 0 1 1

0
5
4

数据范围

$1 <= t <= 100$

$1 <= n <= 1000$