题目描述

一条街上有N家店铺，第i家店铺中有一定数量的现金。阿福可以选择若干家店铺，但不能同时选择两家相邻的店铺，否则会触发警报。

求在不触发警报的前提下，最多可以获得多少现金。

输入格式

第一行整数T。每组数据先输入一个整数N，再输入N个正整数，表示按顺序排列的店铺现金数量。

输出格式

每组数据输出一行，表示最多能够获得的现金。

样例

2
3
1 8 2
4
10 7 6 14

8
24

数据范围

1≤T≤50，1≤N≤100000；每家店铺的现金数量为1至1000。