← 返回题目列表

Codeforces · 1734/A

A. 选择三根棍子

中文机器翻译题面 查看原题

给你 $$$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$$$ 的等边三角形,并由第二、第四和第七根棍子组成。