晾晒的衣物

每个星期天都是洗衣日，总有一大堆衣服等着洗，这肯定会花掉你永远的时间。你特别烦恼的是，在洗某些衣物时必须格外小心，而且为每件衣物选择合适的洗涤程序非常重要。

幸运的是，你的洗衣机虽然很旧，但支持三种不同的洗涤程序：A、B 和 C。你一次最多可以放入 $k$ 件衣物，且每一批次只能使用其中一种程序。

有些衣物很容易打理，你可以把它们放在任何批次中。更精细的衣物不能使用特定的程序，但另外两种程序是可以的。当然，最麻烦的衣服是那些只能使用一种特定程序的衣服。

你已经通过将可以使用相同程序组合的衣物放在一起，将衣物分成了七堆，因此你知道每一堆中有多少件衣物。

你需要洗的最少批次数是多少？

图 L.1：样例 2 的最优解示意图。左图显示了七堆衣物，每堆对应一种组合。右图显示了一个（可能的）最优解，其中每一堆都在一个批次中洗涤。堆上的数字表示该批次中洗涤的每种组合的衣物数量。特别地，最左边的一堆使用程序 A 洗涤，中间的两堆使用程序 B 洗涤，右边的两堆使用程序 C 洗涤。因此，我们需要 5 个批次来洗完所有衣物，考虑到总共有 15 件衣物，这是最优的。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。 对于每个测试用例： 一行包含一个整数 $k$ ($1 \le k \le 10^9$)，表示一个批次中最多可以放入的衣物数量。 一行包含七个整数 $c_1, \dots, c_7$ ($0 \le c_i \le 10^9$)，表示每种程序组合的衣物数量。整数按以下顺序给出：A、B、C、AB、BC、AC、ABC。例如，$c_4$ 必须使用程序 A 或程序 B 洗涤。

输出格式

对于每个测试用例，输出洗完所有衣物所需的最少批次数。

样例

输入格式 1

4
10
15 11 9 5 2 7 1
120
0 0 0 0 0 0 0
6
5 6 8 9 1 0 0
1213
295053681 137950336 87466375 956271897 344992260 31402049 988259763

输出格式 1

6
0
6
2342454

输入格式 2

1
3
1 2 1 3 3 2 3

输出格式 2

5