有三名学生正在为 ICPC 进行刻苦训练。他们正在练习一套恰好包含 $S$ 道题的题集。每道题都恰好属于以下七个类别之一，描述了哪些学生子集可以解决它：

• $F_1$：只有学生 1 可以解决；
• $F_2$：只有学生 2 可以解决；
• $F_3$：学生 1 和 2（但不是 3）可以解决；
• $F_4$：只有学生 3 可以解决；
• $F_5$：学生 1 和 3（但不是 2）可以解决；
• $F_6$：学生 2 和 3（但不是 1）可以解决；
• $F_7$：学生 1、2 和 3 都可以解决。

保证： $$F_1 + F_2 + F_3 + F_4 + F_5 + F_6 + F_7 = S$$

你需要将每道题分配给恰好一名可以解决它的学生。你的目标是使训练尽可能均衡：最大化任何单名学生解决的最小题目数量。输出这个最大可能的值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$) —— 测试用例的数量。

对于每个测试用例： 第一行包含一个整数 $S$ ($0 \le S \le 7 \times 10^8$)。 第二行包含七个非负整数 $F_1, F_2, F_3, F_4, F_5, F_6, F_7$ ($0 \le F_1, \dots, F_7 \le 10^8$)。

保证 $F_1 + \dots + F_7 = S$。

输出格式

对于每个测试用例，输出一个整数 —— 在分配完所有 $S$ 道题后，三名学生中解决题目数量的最小值的最大可能值。

样例

输入样例 1

4
36
14 4 3 2 9 0 4
41
4 8 4 4 3 14 4
53
3 0 12 6 14 11 7
55
11 10 11 10 2 8 3

输出样例 1

11
13
17
18