给你 $$$n$$$ 正整数长度 $$$a_1, a_2, \ldots, a_n$$$ 的棍子。
您可以执行以下操作任意次数(可能为零):
- 选择一根棍子,然后将其长度增加或减少$$$1$$$。每次操作后,所有棒都应具有正长度。
您需要执行的最少操作次数是多少,才能选择 $$$n$$$ 棍子中的三根并使用它们而不折断以形成等边三角形?
等边三角形是三个边都具有相同长度的三角形。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 300$$$) — 木棍的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 木棍的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$300$$$。
输出
对于每个测试用例,在一行上打印一个整数 - 要进行的最少操作数。
示例
输入 #1
4 3 1 2 3 4 7 3 7 3 5 3 4 2 1 1 8 3 1 4 1 5 9 2 6
输出 #1
2 4 1 1
注意
在第一个测试用例中,您可以将第一根棍子的长度增加$$$1$$$,然后将第三根棍子的长度减少$$$1$$$。总共,您执行 $$$2$$$ 操作,使得三根棍子形成边长 $$$2$$$ 的等边三角形。
在第四个测试用例中,您可以将第七根棍子的长度减少$$$1$$$。可以选择边长为 $$$1$$$ 的等边三角形,并由第二、第四和第七根棍子组成。