Min_sum_partition

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
	public static void main (String[] args) {
		//code
		Scanner o=new Scanner(System.in);
        int t=o.nextInt();
        for(int i=0;i<t;i++){
            int n=o.nextInt();
            int arr[]=new int[n];
            int sum=0;
            for(int j=0;j<n;j++){
                arr[j]=o.nextInt();
                sum+=arr[j];
            }
            System.out.println(minDiff(arr,n,sum));
        }
	}
	
	public static int minDiff(int arr[],int n,int range){
	    ArrayList<Integer> list=subset(arr,n,range);
	    int min=Integer.MAX_VALUE;
	    for(int i=0;i<list.size();i++){
	        int temp=range-2*list.get(i);
	        min=Math.min(min,temp);
	    }
	    return min;
	}
	
	public static ArrayList<Integer> subset(int arr[],int n, int sum){
	    boolean dp[][]=new boolean[n+1][sum+1];
	    for(int i=0;i<=sum;i++){
	        dp[0][i]=false;
	    }
	    
	    for(int i=0;i<=n;i++){
	        dp[i][0]=true;
	    }
	    
	    for(int i=1;i<=n;i++){
	        for(int j=1;j<=sum;j++){
	            if(arr[i-1]<=j){
	                dp[i][j]=dp[i-1][j-arr[i-1]] || dp[i-1][j];
	            }
	            else{
	                dp[i][j]=dp[i-1][j];
	            }
	        }
	    }
	    
	    ArrayList<Integer> l=new ArrayList<>();
	    for(int j=0;j<=sum/2;j++){
	        if(dp[n][j]){
	            l.add(j);
	        }
	    }
	    
	    return l;
	}
	
}