빨래

매주 일요일은 빨래하는 날이고, 세탁을 기다리는 옷이 언제나 산더미처럼 쌓여 있다. 이 일은 분명 오래 걸린다. 특정 옷은 세탁할 때 특히 조심해야 해서, 옷마다 알맞은 세탁 프로그램을 고르는 일이 중요하고 번거롭다.

다행히 세탁기는 꽤 오래되었고 A, B, C 세 가지 프로그램만 지원한다. 한 번에 최대 $k$개의 옷을 넣을 수 있고, 각 세탁 횟수마다 세 프로그램 중 하나를 골라 돌린다.

어떤 옷은 관리가 쉬워서 원하는 세탁 횟수에 아무 때나 넣어도 된다. 더 섬세한 옷은 특정 프로그램으로 세탁하면 안 되고, 나머지 두 프로그램은 써도 된다. 가장 까다로운 옷은 적합한 프로그램이 하나뿐인 옷이다.

옷은 이미 일곱 묶음으로 나누어 두었다. 같은 묶음에 든 옷은 허용되는 프로그램 조합이 같다. 각 묶음에 옷이 몇 개인지도 알고 있다.

모든 옷을 세탁하는 데 필요한 최소 세탁 횟수는 몇 번인가?

그림 L.1: 최적해가 있는 예제 입력 2의 그림. 왼쪽 그림은 조합마다 하나씩, 총 일곱 묶음을 보여준다. 오른쪽 그림은 최적해 중 하나로, 각 묶음을 한 번의 세탁으로 처리한다. 묶음 위의 숫자는 그 세탁에 들어가는 조합별 옷의 개수다. 가장 왼쪽 묶음은 A 프로그램으로, 가운데 두 묶음은 B 프로그램으로, 오른쪽 두 묶음은 C 프로그램으로 세탁한다. 옷이 모두 15개이므로 세탁은 5번 필요하고, 이것이 최적이다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \leq t \leq 10^4$)가 주어진다. 각 테스트 케이스는 다음과 같다.

• 한 줄에 정수 $k$ ($1 \leq k \leq 10^9$)가 주어진다. 한 번의 세탁에 넣을 수 있는 옷의 최대 개수다.
• 한 줄에 정수 일곱 개 $c_1, \ldots, c_7$ ($0 \leq c_i \leq 10^9$)이 주어진다. 순서대로 A, B, C, AB, BC, AC, ABC 묶음의 옷 개수다. 예를 들어 $c_4$의 옷은 A 또는 B 프로그램 중 하나로 세탁해야 한다.

각 테스트 케이스마다 모든 옷을 세탁하는 데 필요한 최소 세탁 횟수를 한 줄에 출력한다.