题目描述

小珅面前有 $n$ 个糖果排成一行，从左到右第 $i$ 个糖的价值是 $a_{i}$。

小珅打算拿走一些糖，但是他不愿意拿走两个相邻的糖。

你要求出，在不同时拿走任意相邻的糖的前提下，小珅最多能拿走多少价值的糖？

输入格式

第一行一个整数 $T$，表示有 $T$（$1\le T\le50$）组数据。

接下来的每组数据，第一行是一个整数 $n$（$1\le n\le10^5$），表示一共有 $n$ 个糖。

第二行是 $n$ 个被空格分开的正整数，表示每个糖的价值，不超过 $1000$。

输入量较大，请使用 scanf 或者将 cin 关闭流同步。

输出格式

对于每组数据，输出一行。

该行包括一个整数，表示在不同时拿走任意相邻的糖的前提下，最多能拿走的糖的价值。

说明与提示

对于第一组样例，拿第 $2$ 个糖，总价值为 $8$。

对于第二组样例，拿第 $1$ 和 $4$ 个糖，总价值为 $10+14=24$。

来源

浩轩OJ 4387 · 原题图片

数据范围与约定

$1\le T\le50$，$1\le n\le10^5$。每个糖的价值不超过 $1000$。

可见测试数据

输入数据 1

2
3
1 8 2
4
10 7 6 14

输出数据 1

8
24

输入数据 2

1
1
1

输出数据 2

1

输入数据 3

1
1
1000

输出数据 3

1000