← 返回题目列表

Codeforces · 1620/D

D. 确切的变化

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

有一天,一大早,您决定在附近的商店给自己买一袋薯片。店里有$$$n$$$不同口味的薯条。一袋 $$$i$$$ 口味的价格为 $$$a_i$$$ burles。

商店里的某些口味可能会卖完,所以你到店后再决定购买哪一种。但这个计划有两个重大缺陷:

1. 您只有 $$$1$$$、$$$2$$$ 和 $$$3$$$ burles 的硬币;
2. 由于是早上,商店会要求您准确支付零钱,即。 e.如果您选择第$$$i$$$口味,则必须支付$$$a_i$$$ burles。

硬币很重,因此您希望总共拿走尽可能少的硬币。这就是为什么您想知道:您应该随身携带的硬币最少总数是多少,这样您就可以用零钱购买一袋任何口味的薯条?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 商店中的口味数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 每种口味一袋的成本。

输出

对于每个测试用例,打印一个整数 - 购买一袋您选择的任何口味所需的最小硬币数量。

示例

输入 #1

4
1
1337
3
10 8 10
5
1 2 3 4 5
3
7 77 777

输出 #1

446
4
3
260

注意

在第一个测试用例中,例如,您应该随身携带价值 $$$3$$$ 的 $$$445$$$ 硬币和价值 $$$2$$$ 的 $$$1$$$ 硬币。所以,$$$1337 = 445 \cdot 3 + 1 \cdot 2$$$。

在第二个测试用例中,例如,您应该获取价值 $$$3$$$ 的 $$$2$$$ 硬币和价值 $$$2$$$ 的 $$$2$$$ 硬币。因此,您可以支付 $$$8 = 2 \cdot 3 + 1 \cdot 2$$$ 或 $$$10 = 2 \cdot 3 + 2 \cdot 2$$$。

在第三个测试用例中,获取价值 $$$3$$$ 的 $$$1$$$ 硬币和价值 $$$1$$$ 的 $$$2$$$ 硬币就足够了。