题目描述

商店里有 $n$ 件商品，按照给定顺序从 $1$ 到 $n$ 编号，第 $i$ 件商品的价格为 $a_i$ 元。

你需要购买全部 $n$ 件商品。你有一张优惠券，可以选择两件编号相邻的商品，使这两件商品同时免单。

编号相邻指编号分别为 $i$ 和 $i+1$，其中 $1\le i<n$。商品的编号和顺序都不能改变。

优惠券至多使用一次。请问购买全部商品最少需要支付多少钱？

输入格式

第一行包含一个整数 $t$ ($1\le t\le10^4$)，表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$ ($2\le n\le2\times10^5$)，表示商品数量；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le10^9$)，表示各件商品的价格。

数据保证所有测试用例的 $n$ 之和不超过 $2\times10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示购买全部商品最少需要支付的金额。

4
5
3 8 2 9 4
2
7 11
3
100 1 100
5
1000000000 1000000000 1000000000 1000000000 1000000000

13
0
100
3000000000

样例解释

第一组测试用例中，可以让第 $4$ 件和第 $5$ 件商品免单，需要支付 $3+8+2=13$ 元。

第二组测试用例中，两件商品可以同时免单，因此无需支付费用。

第三组测试用例中，第 $1$ 件和第 $3$ 件商品的编号不相邻，不能同时免单。可以让第 $1$ 件和第 $2$ 件商品免单，需要支付 $100$ 元。

第四组测试用例中，任意两件编号相邻的商品免单后，都还需要支付另外三件商品的费用。