레이팅 미적용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 \(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?
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.
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