题目描述

   听说初赛doubi来捧(za)场(chang)了？！听说doubi瞬间就登顶了？！听说无所事事的doubi，只好找来了许多食物，坐在床上吃东西？！

  其实doubi是3个人，食物不超过20份，他们给每一份食物都打了分。现在他们正在纠结，怎么分配这些食物，才能使每个人分到的食物总分尽可能平均。假设3-doubi得到的食物总分是a,b,c，就用 max(a,b,c)−min(a,b,c)

评价分配方案的好坏。

  现在请你告诉我，doubi的食物分配方案中， max(a,b,c)−min(a,b,c)

最小是多少。

输入

   第一行一个整数T，表示有T组测试数据。

  每组测试数据2行，第一行一个整数N，表示有N份食物。第二行N个正整数， X

i

表示第i份食物的评分。

  T≤20,1≤N≤20,1≤X

i

≤10

7

  只有一组数据 N=20

，其余 N≤16

。

输出

   每组数据输出一行，只有一个整数，表示3个doubi的食物分数差异的最小值。

样例输入

样例输出

#include
      
       using namespace std;void BubbleSort( unsigned int *a ,int n){	for(int i=n-1;i>0;i--)	  for(int j=0;j
       
        a[1])	   min=1;	   if(a[min]>a[2])	   min=2;	  return a[max]-a[min];}int main() {	int n,m; unsigned int a[1024];  unsigned int b[4]={		0	};		cin>>n;	for(int x=0;x
        
         >m;      			for(int i=0;i
         
          >a[i];		}		a[m]='\0';		BubbleSort(a,m);		b[0]=a[0];		b[1]=a[1];		b[2]=a[2];		b[3]='\0';				int result,u,o;		 unsigned int  temp[4]; unsigned int temp1[4];		for(int z=3;z
          
           result){    			b[2]+=a[z];    			BubbleSort(b,3);    		}else    		{		    	b[1]+=a[z];		    	BubbleSort(b,3);		    }		    		}		cout<