一天，上课的时候小L老师带来一些食物，要把它分给同学们品尝，于是这些食物被分成了n堆。每一堆都给它标注了一个价值。
小L老师就问同学们如何选择品尝的顺序使得品尝的价值之和最大。聪明的你立马就想到了把所有的食物品尝一遍价值和就是最大。
这时小L老师立马加了一个规矩不能品尝相邻的两种食物，例如食物A B C依次摆放着桌子上，当你品尝了食物A 你就不能品尝食物B。
下一个品尝的食物只能是C。当你品尝了食物B，你就不能品尝食物C，同时也不能品尝食物A。聪明的你知道如何选择使得你从左到
右选择品尝的食物的价值最大嘛！最大的价值是多少。
输入描述:
第一行一个整数T（1≤T≤500），表示共有T组测试数据。
对于每组数据，第一次一个数字n（1≤n≤1000）表示有n堆食物接下来一行有n个数，分别表示每堆食物的价值ai (0≤ai≤100).
输出描述:
输出一个整数代表所能获得的最大价值
示例1
说明
样例一 选择品尝第二个和第四个食物获得的价值总和最大为6