A. 数组的价值(value)

给你一个由0和1组成的长度为n的数组a，你可以把这个数组分成若干连续的非空段，每段的贡献是将这段数字排序后的中位数。本题中位数的定义:按顺序排列的一组数据中居于中间位置的数。对于任意一个序列求中位数时:

第一步:先对数组进行排序;

第二步: 如果序列长度为奇数，则取中间那个数字。例如: {0，0，1，1，1}，中位数为1; 如果序列长度为偶数，则取中间两个数字的平均数向下取整的结果。例如:{0，0，1，1}，中位数为(0+1)÷2向下取整的结果:0。

该数组的价值是指每段贡献总和，对于该数组的不同划分方式的得到价值是不相同的，请你求出最小的价值。

每个测试点共有T组测试数据。

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

对于每组数据:

第—行—个整数n，表示数组长度。

第二行—共包含n个整数，分别表示表示a数组。

输出共T行，每行输出—个整数。

第i行的整数表示第i组测试数据中求出的最小价值。

样例输入1

2
3
0 1 1
4
0 1 0 1

样例输出1

1
0

对于100%的数据，。