一排有 $$$n$$$ 块塔,其中塔 $$$i$$$ 的高度为 $$$a_i$$$。您是建筑团队的一员,您希望使建筑物看起来尽可能漂亮。在一天之内,您可以执行以下操作:
- 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$),并将一个方块从塔 $$$i$$$ 移到塔 $$$j$$$。这实际上使 $$$a_i$$$ 减少了 $$$1$$$,并增加了 $$$a_j$$$ $$$1$$$。
你认为建筑物的丑陋在于最高和最矮建筑物之间的高度差。正式地,丑陋被定义为$$$\max(a)-\min(a)$$$。
在任意天数之后,您能达到的最低限度的丑陋程度是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 建筑物的数量。
每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$) — 建筑物的高度。
输出
对于每个测试用例,输出一个整数 - 建筑物的最小可能的丑陋程度。
示例
输入 #1
3 3 10 10 10 4 3 2 1 2 5 1 2 3 1 5
输出 #1
0 0 1
注意
在第一个测试用例中,丑陋程度已经是$$$0$$$。
在第二个测试用例中,您应该执行一个操作,其中 $$$i = 1$$$ 和 $$$j = 3$$$。新的高度现在为 $$$[2, 2, 2, 2]$$$,丑陋度为 $$$0$$$。
在第三个测试用例中,您可以执行三个操作:
1. $$$i = 3$$$ 且 $$$j = 1$$$。新数组现在将为 $$$[2, 2, 2, 1, 5]$$$,
2. $$$i = 5$$$ 且 $$$j = 4$$$。新数组现在将为 $$$[2, 2, 2, 2, 4]$$$,
3. $$$i = 5$$$ 且 $$$j = 3$$$。新数组现在将为 $$$[2, 2, 3, 2, 3]$$$。