C. Jiaxun!
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are three students training hard for ICPC. They are practicing on a problemset consisting of exactly $$$S$$$ problems. Each problem belongs to exactly one of the following seven categories, describing which subset of students can solve it:

  • $$$F_1$$$: only student $$$1$$$ can solve;
  • $$$F_2$$$: only student $$$2$$$ can solve;
  • $$$F_3$$$: students $$$1$$$ and $$$2$$$ (but not $$$3$$$) can solve;
  • $$$F_4$$$: only student $$$3$$$ can solve;
  • $$$F_5$$$: students $$$1$$$ and $$$3$$$ (but not $$$2$$$) can solve;
  • $$$F_6$$$: students $$$2$$$ and $$$3$$$ (but not $$$1$$$) can solve;
  • $$$F_7$$$: students $$$1$$$, $$$2$$$ and $$$3$$$ can all solve.

It is guaranteed that $$$$$$ F_1 + F_2 + F_3 + F_4 + F_5 + F_6 + F_7 = S. $$$$$$

You are going to assign each problem to exactly one student who can solve it. Your goal is to make the training as balanced as possible: maximize the minimum number of problems solved by any single student. Output this maximum possible value.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$)— the number of test cases.

For each test case, the first line contains a single integer $$$S$$$ ($$$0 \leq S \leq 7 \times 10^8$$$).

The second line contains seven non-negative integers $$$F_1, F_2, F_3, F_4, F_5, F_6, F_7$$$ ($$$0 \le F_1, \cdots, F_7 \le 10^{8}$$$).

It is guaranteed that $$$F_1 + \cdots + F_7 = S$$$.

Output

For each test case, print a single integer — the maximum possible value of the minimum solved-count among the three students after assigning all $$$S$$$ problems.

Example
Input
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
Output
11
13
17
18