1096: 疲惫的Junjie An
Description
某天 Junjie An 刚刚刷完题目觉得有些口渴，决定去附近的商店买一瓶可乐。商店里有 $n$ 种不同口味的可乐。一瓶 i -th口味的售价为 $a_i$。
商店里有些口味的可乐可能会卖完，所以你要在到达商店后再决定买哪一种。但这个计划有两个局限：
1.你只有 $1, 2$ 和 $3$ 种价值的硬币；
2.要求你用零钱付款，也就是说，如果你选择 i-th口味，你就必须支付恰好 $a_i$ 的钱。
因为 Junjie An 太疲惫了，所以 Junjie An 希望尽可能少带硬币。Junjie An 想知道为了能买得起任何口味的一瓶可乐，应该带的硬币总数最少是多少？
Input
第一行包含一个整数 $t$$(1 \leq t \leq 1000)$ - 测试用例数。
每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 100)$ 表示商店中的口味数量。
每个测试用例的第二行包含 n个整数 $a_1$,$a_2$,…,$a_n$ 。$ (1 \leq a_i \leq 10^9) $ 表示每种口味的售价。
Output
对于每个用例，输出一行一个整数代表答案
Sample Input Copy
3
1
2000
5
1 2 3 4 5
3
7 77 777
Sample Output Copy
667
3
260
HINT
在第一个测试案例中，选择携带价值 $3$ 的 $666$ 枚硬币和价值 $2$ 的 $1$ 枚硬币即可，因为 $2000$ 由 $666$ 个 $3$ 块的硬币和 $1$ 个 $2$ 块的硬币可以合成 $(2000=666 \times 3+1 \times 2)$
在第二个测试案例中，选择携带价值 $3$ 的 $1$ 枚硬币和价值 $1$ 的 $2$ 枚硬币即可， $4$ 由 $1$ 个 $3$ 块的硬币和 $1$ 个 $1$ 块的硬币可以合成 $(4=1+3)$ , $5$ 由 $2$ 个 $1$ 块的硬币和 $1$ 个 $3$ 块的硬币可以合成 $(5=2 \times 1+3)$
在第二个测试案例中，选择携带价值 $3$ 的 $258$ 枚硬币和价值 $2$ 的 $1$ 枚硬币和价值 $1$ 的 $1$ 枚硬币即可， $7$ 由 $2$ 个 $3$ 块的硬币和 $1$ 个 $1$ 块的硬币可以合成 $(7=3+3+1)$ ， $77$ 由 $25$ 个 $3$ 块的硬币和 $1$ 个 $2$ 块的硬币可以合成$(77=25 \times 3+2)$ ， $777$ 由 $258$ 个 $3$ 块的硬币和 $1$ 个 $1$ 块的硬币和 $1$ 个 $2$ 块的硬币可以合成 $(777=258 \times 3+2+1)$