我什么都做得到

题目描述

小三月跟随列车组来到了匹诺康尼--梦的国度。（由于出题人在命题的时候还没进入$2.0$，所以他正好只好肆意妄想一下。）

匹诺康尼的梦境世界都是由$01$构成的，比如说$3$就是$11$，$7$就是$111$，$37$就是$100101$等。当然，它们的前面都可以有任意多个$0$.

“既然在梦里，那我岂不是什么都做得到！”，小三月这么想着。于是她就梦到了这样的操作规则：对于两个数字，首先得出构成它们的$01$串，然后她可以交换二者从后往前相同位置的数字。比如说，$111$和$100101$交换第$2$位就是$(101,100111)$，交换第$6$位就是$(100111,101).$

现在你在小三月的梦境中看到了$n$个数字，你可以通过小三月给出的规则不断改变这$n$个数字，并希望给出最大的极差。

极差：一个列表的极差指的是它的最大值减去最小值。

数据格式

输入

第一行，一个正整数$T$. 表示测试用例的组数。

每组测试用例两行。

第一行，一个正整数$n$.

第二行，$n$个正整数$a_i$。

输出

通过小三月的规则可以得出的最大极差。

样例

输入

4
3
1 0 1
4
5 5 5 5
5
1 2 3 4 5
7
20 85 100 41 76 49 36

输出

1
0
7
125

数据范围及约定

$T \le 10^4$

$\sum n \le 10^5$

$a_i \le 10^9$