package no3185_three_abs; import java.util.*; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); StringBuilder sb = new StringBuilder(); for(int c = 0;c < t;c++) { int n = sc.nextInt(); int[] a = new int[n + 1]; for(int i = 1;i <= n;i++) { a[i] = sc.nextInt(); }//dp[今いる区間について足しているor引いている][今いる区間] long[][] dpOld = new long[2][3]; for(int i = 1;i <= n;i++) { long[][] dp = new long[2][3]; for(int p = 0;p < 2;p++) { for(int q = 0;q < 3;q++) { dp[p][q] = Long.MIN_VALUE/2; } }//区間移動が発生しない for(int p = 0;p < 3;p++) { dp[1][p] = Math.max(dp[1][p], dpOld[1][p] - a[i]); dp[0][p] = Math.max(dp[0][p], dpOld[0][p] + a[i]); }//発生する if(i != n) { for(int p = 0;p < 2;p++) { dp[0][p + 1] = Math.max(dp[0][p + 1], dpOld[1][p] - a[i]); dp[0][p + 1] = Math.max(dp[0][p + 1], dpOld[0][p] + a[i]); dp[1][p + 1] = Math.max(dp[1][p + 1], dpOld[1][p] - a[i]); dp[1][p + 1] = Math.max(dp[1][p + 1], dpOld[0][p] + a[i]); } }dpOld = dp; }sb.append(Math.max(dpOld[0][2], dpOld[1][2]) + "\n"); }System.out.print(sb); } }