import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.FileReader;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;

public class casino_va implements Runnable {
    public static void main(String[] args) {
        new Thread(new casino_va()).run();
    }

    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;

    public String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }

        return in.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public int solve(int[] a) throws IOException {
        int n = a.length;

        if (n == 1)
            return 0;

        int[] ans = new int[n];

        ans[1] = Math.max(2 * a[0], 2 * a[1]);

        for (int i = 2; i < n; i++) {
            int max = a[i];
            int sum = 0;
            for (int j = i - 1; j >= 2; j--) {
                max = Math.max(max, a[j]);
                ans[i] = Math.max(ans[i], ans[j - 2] + 2 * (sum + max) + (a[j] + a[j - 2]));
                sum += a[j];
            }
            max = Math.max(max, a[0]);
            max = Math.max(max, a[1]);
            sum += a[1];
            ans[i] = Math.max(ans[i], 2 * (sum + max));
            ans[i] = Math.max(ans[i], ans[i - 2] + (a[i] + a[i - 2]));
        }
        System.err.println(Arrays.toString(ans));
        return ans[n - 1];
    }

    public class State {
        int i;
        int sum;
        int max;
        int prefix;
        int add;

        public State(int i, int sum, int max) {
            this.i = i;
            this.sum = sum;
            this.max = max;
        }

        public String toString() {
            return i + " " + (0.5 * sum) + " " + max + " " + prefix + " " + (0.5 * add);
        }
    }

    public int solve2(int[] a) throws IOException {
        int n = a.length;

        if (n == 1)
            return 0;

        Stack<State> stack = new Stack<State>();

        int[] ans = new int[n];

        ans[1] = 2 * Math.max(a[0], a[1]);

        stack.push(new State(0, 0, Math.max(a[0], a[1])));
        stack.peek().prefix = 2 * Math.max(a[0], a[1]);

        for (int i = 2; i < n; i++) {
            State top = stack.peek();
            top.add += 2 * a[i - 1];

            State newState;
            if (i == 2) {
                newState = new State(1, 2 * a[1], a[1]);
            } else {
                newState = new State(i - 1, a[i - 1] + a[i - 3] + ans[i - 3], a[i - 1]);
            }
            newState.prefix = newState.sum + 2 * newState.max;
            if (!stack.isEmpty()) {
                newState.prefix = Math.max(newState.prefix, stack.peek().prefix + stack.peek().add);
            }
            stack.push(newState);

//            System.err.println("Before sieving " + stack);

            //sieve of a[i] as maximum
            int max = 0;
            int bi = -1;
            int add = 0;
            while (!stack.isEmpty() && stack.peek().max <= a[i]) {
                State state = stack.pop();
                add += state.add;
                if (max < state.sum + add) {
                    max = Math.max(max, state.sum + add);
                    bi = state.i;
                }
            }
            if (bi != -1) {
                State state = new State(bi, max, a[i]);

                state.prefix = state.sum + 2 * state.max;
                if (!stack.isEmpty()) {
                    stack.peek().add += add;
                    state.prefix = Math.max(stack.peek().prefix + stack.peek().add, state.prefix);
                }

                stack.push(state);

                ans[i] = state.prefix;
            } else {
                ans[i] = stack.peek().prefix + stack.peek().add;
            }
            ans[i] = Math.max(ans[i], ans[i - 2] + (a[i] + a[i - 2]));
//            System.err.println("After sieving: " + stack);
        }

//        System.err.println(Arrays.toString(ans));               //

        return ans[n - 1];
    }

    public void run() {
        try {
            //br = new BufferedReader(new InputStreamReader(System.in));
            //out = new PrintWriter(System.out);
            br = new BufferedReader(new FileReader("casino.in"));
            out = new PrintWriter("casino.out");
        
            Random rnd = new Random(239);
       /*     while (true) {
                int[] a = new int[rnd.nextInt(100) + 1];
                for (int i = 0; i < a.length; i++) {
                    a[i] = rnd.nextInt(100) + 1;
                }

                int ans1 = solve(a);
                int ans2 = solve2(a);
                if (ans1 != ans2) {
                    System.err.println(ans1 + " " + ans2);
                    System.out.println(a.length);
                    for (int i = 0; i < a.length; i++) {
                        System.out.print(a[i] + " ");
                    }
                    break;
                }
            }                            */

        int t = nextInt();
    while (t-- > 0) {
            int n = nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            int ans = solve(a);
            out.println(.5 * ans);
       }
           /* ans = solve(a);
            out.println(.5 * ans);
                             */
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
}
