package 线性dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
 * 这条街上一共有 N家店铺，每家店中都有一些现金。
 * 阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
 * 作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
 * 他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
 * 输入的第一行是一个整数 T，表示一共有 T组数据。
 * 接下来的每组数据，第一行是一个整数 N，表示一共有 N家店铺。
 * 第二行是 N个被空格分开的正整数，表示每一家店铺中的现金数量。
 * 每家店铺中的现金数量均不超过1000。
 * 输出格式
 * 对于每组数据，输出一行。
 * 该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
 * 数据范围
 * 1≤T≤50,
 * 1≤N≤10^5
 * 输入样例：
 * 2
 * 3
 * 1 8 2
 * 4
 * 10 7 6 14
 * 输出样例：
 * 8
 * 24
 * 样例解释
 * 对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。
 * 对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。
 * 分析：
 * 方法一：线性DP
 * 作为一个典型的线性dp问题，本题可以用线性DP的解法来解决。
 * 状态表示f[i]表示在前i家店铺中能够获得的最多的现金。
 * 如果第i家店铺不洗劫，则获得的现金与在前i-1家店铺获得的最大现金一致，
 * 即f[i] = f[i-1]；如果第i家店铺洗劫，则第i-1家店铺不能洗劫，
 * 否则会触发报警器，故此时f[i] = f[i-2] + w，w表示洗劫第i家店铺可以获得的现金。
 * 故状态转移方程为f[i] = max(f[i-1],f[i-2]+w),i >= 2。
 * 这里的边界状态为f[0] = 0,f[1] = w1，因为只有一家商铺时选择洗劫必然是最优选择。
 */
public class 大盗阿福 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        while (t-- != 0) {
            n = sc.nextInt();
            Arrays.fill(dp, 0);
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            dp[1] = a[0];
            for (int i = 2; i <= n; i++) {
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i - 1]);
            }
            System.out.println(dp[n]);
        }
    }

    static int[] dp = new int[100050];
    static int[] a = new int[100050];
    static int t, n;
}