有一天,一大早,您决定在附近的商店给自己买一袋薯片。店里有$$$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$$$ 硬币就足够了。