Problem K
Laundry

Laundry hanging to dry
Image by gregroose on Pixabay

Fortunately, your washing machine is quite old and only supports three different washing programmes: A, B, and C. You can put at most $k$ items in one load, and each load can be washed using one of the programmes.

Some items are easy to care for, and you can put them in any load you like. More delicate items must not be washed using a specific programme, but the other two are fine. Of course, the worst clothes are the ones for which only one programme is appropriate.

You have already sorted the items into seven piles by putting items together for which the same combination of programmes is fine, so you know how many items are in each pile.

What is the minimum number of loads you need to wash?

Figure 1: Illustration of Sample Input 2 with an optimal solution. The figure on the left shows seven piles, one for each combination. The figure on the right shows a (possible) optimal solution, where each pile is washed in one load. The numbers on the pile represent how many items of each combination are washed with this load. In particular, the leftmost pile is washed using programme A, the two piles in the middle with programme B, and the two piles on the right with programme C. Thus, we need five loads to wash all items, which is optimal since we have $15$ items in total.

Input

The input starts with a line containing one integer $t$ ($1 \leq t \leq 10^4$), the number of test cases. Then for each test case:

• One line with an integer $k$ ($1\leq k\leq 10^9$), the number of items you can put in one load.

• One line with seven integers $c_1, \ldots , c_7$ ($0 \leq c_i \leq 10^9$), the number of items for each combination of programmes. The integers are given in this order: A, B, C, AB, BC, AC, ABC. For example, $c_4$ must be washed using either programme A or programme B.

Output

For each test case, output the minimum number of loads that are needed to wash all clothes.

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

6
0
6
2342454

1
3
1 2 1 3 3 2 3

5