CF1620D.Exact Change

One day, early in the morning, you decided to buy yourself a bag of chips in the nearby store. The store has chips of $n$ different flavors. A bag of the $i$-th flavor costs $a_i$ burles.

The store may run out of some flavors, so you'll decide which one to buy after arriving there. But there are two major flaws in this plan:

1. you have only coins of $1$, $2$ and $3$ burles;
2. since it's morning, the store will ask you to pay in exact change, i. e. if you choose the $i$-th flavor, you'll have to pay exactly $a_i$ burles.

Coins are heavy, so you'd like to take the least possible number of coins in total. That's why you are wondering: what is the minimum total number of coins you should take with you, so you can buy a bag of chips of any flavor in exact change?

一天清晨，你决定去附近的商店买一袋薯片。这家商店有 $n$ 种不同口味的薯片，第 $i$ 种口味的一袋售价为 $a_i$ 卢布。

由于商店可能会售罄某些口味，你将在抵达商店后才决定购买哪一种。但该计划存在两个主要问题：

1. 你身上只有面值为 $1$、$2$ 和 $3$ 卢布的硬币；
2. 由于是早晨，商店要求你必须支付恰好的金额，即：如果你选择第 $i$ 种口味，你就必须恰好支付 $a_i$ 卢布。

硬币很重，因此你希望携带的硬币总数尽可能少。正因如此，你开始思考：为了能够用恰好的金额购买任意一种口味的薯片，你最少需要随身携带多少枚硬币？

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \le n \le 100$) — the number of flavors in the store.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the cost of one bag of each flavor.

第一行包含一个整数 $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$）—— 每种口味一袋冰淇淋的价格。

For each test case, print one integer — the minimum number of coins you need to buy one bag of any flavor you'll choose in exact change.

对于每个测试用例，输出一个整数——即你需要的最少硬币数量，以便恰好支付你所选择的任一口味的一袋零食。

In the first test case, you should, for example, take with you $445$ coins of value $3$ and $1$ coin of value $2$. So, $1337 = 445 \cdot 3 + 1 \cdot 2$.

In the second test case, you should, for example, take $2$ coins of value $3$ and $2$ coins of value $2$. So you can pay either exactly $8 = 2 \cdot 3 + 1 \cdot 2$ or $10 = 2 \cdot 3 + 2 \cdot 2$.

In the third test case, it's enough to take $1$ coin of value $3$ and $2$ coins of value $1$.

在第一个测试用例中，例如，你可以携带 $445$ 枚面值为 $3$ 的硬币和 $1$ 枚面值为 $2$ 的硬币。因此，$1337 = 445 \cdot 3 + 1 \cdot 2$。

在第二个测试用例中，例如，你可以携带 $2$ 枚面值为 $3$ 的硬币和 $2$ 枚面值为 $2$ 的硬币。因此，你可以恰好支付 $8 = 2 \cdot 3 + 1 \cdot 2$ 或 $10 = 2 \cdot 3 + 2 \cdot 2$。

在第三个测试用例中，只需携带 $1$ 枚面值为 $3$ 的硬币和 $2$ 枚面值为 $1$ 的硬币即可。