Laundry

문제

Every Sunday is laundry day, and there is always a huge pile of clothes waiting to be washed, which is certainly going to take you forever. You are particularly annoyed by how careful you have to be when washing certain items, and how important it is that you choose an appropriate washing programme for each item.

Fortunately, your washing machine is quite old and only supports three different washing programmes: A, B, and C. You can put at most $kk$ 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 L.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 $1515$ items in total.

입력

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

• One line with an integer $kk$ ($1\le k\le {10}^{9}1\backslash leq\; k\backslash leq\; 10^9$), the number of items you can put in one load.
• One line with seven integers $c_1,\dots ,c_{7}c\_1,\; \backslash ldots,\; c\_7$ ($0\le c_i\le {10}^{9}0\; \backslash leq\; c\_i\; \backslash 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}c\_4$ must be washed using either programme A or programme B.

출력

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