CF1620D Exact Change

一天清晨，你决定去附近的商店买一包薯片。商店里有 $n$ 种不同口味的薯片。一包第 $i$ 种口味的薯片售价为 $a_i$ 布尔。 商店的某些口味可能会售罄，所以你打算到店后再决定买哪一种。但你的计划有两个主要问题： 1. 你只有面值为 $1$、$2$ 和 $3$ 布尔的硬币； 2. 由于是早上，商店要求你必须用刚好等于售价的零钱支付，也就是说，如果你选择第 $i$ 种口味，你必须正好支付 $a_i$ 布尔。 硬币很重，所以你希望带的硬币总数尽可能少。因此，你想知道：你至少需要带多少枚硬币，才能保证无论选择哪种口味，都能用零钱正好支付？

第一行包含一个整数 $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$），表示每种口味薯片的售价。

对于每个测试用例，输出一个整数，表示你至少需要带多少枚硬币，才能保证可以用零钱正好买到任意一种口味的薯片。

在第一个测试用例中，你可以带 $445$ 枚面值为 $3$ 的硬币和 $1$ 枚面值为 $2$ 的硬币。这样，$1337 = 445 \times 3 + 1 \times 2$。 在第二个测试用例中，你可以带 $2$ 枚面值为 $3$ 的硬币和 $2$ 枚面值为 $2$ 的硬币。这样你可以正好支付 $8 = 2 \times 3 + 1 \times 2$ 或 $10 = 2 \times 3 + 2 \times 2$。 在第三个测试用例中，只需带 $1$ 枚面值为 $3$ 的硬币和 $2$ 枚面值为 $1$ 的硬币即可。 由 ChatGPT 4.1 翻译