Ratatouille (Small)

라따뚜이 요리법을 완성했다. 재료는 $N$가지이고, 재료마다 한 인분에 몇 그램이 필요한지 알고 있다. 이 요리법을 키트로 만들어 팔려고 한다.

재료 꾸러미는 이미 주문해 두었다. 꾸러미 하나에는 재료 한 가지가 일정량 들어 있고, 같은 재료라도 꾸러미마다 들어 있는 양이 다를 수 있다. 재료마다 꾸러미를 $P$개씩 똑같이 주문했다.

키트 하나에는 재료마다 꾸러미를 정확히 하나씩 담고, 몇 인분을 만들 수 있는지 적은 라벨을 붙인다. 라벨에 적는 인분 수는 정수다. 손님에게 모자라게 주지도 않고 재료를 남기지도 않으려면, 키트에 담은 꾸러미의 양이 라벨에 적힌 인분 수에 실제로 필요한 양의 90% 이상 110% 이하여야 한다.

예를 들어 한 인분에 토마토 500 g과 양파 300 g이 필요하고, 토마토 900 g 꾸러미와 양파 660 g 꾸러미가 있다고 하자. 이 둘로 2인분 라벨을 붙인 키트를 만들 수 있다. 2인분에는 토마토 1000 g과 양파 600 g이 필요한데, 900 g은 1000 g의 90%이고 660 g은 600 g의 110%다. 같은 두 꾸러미에 1인분이나 3인분 라벨을 붙일 수는 없고, 라벨은 정수여야 하므로 1.999인분도 붙일 수 없다.

어떤 라벨을 붙여도 키트가 되지 않는 조합도 있다. 같은 요리법에서 토마토 1500 g 꾸러미와 양파 809 g 꾸러미를 보자. 3인분에는 토마토 1500 g과 양파 900 g이 필요한데, 양파 809 g은 900 g의 90%인 810 g에 못 미친다. 다른 정수 인분 수도 모두 맞지 않는다.

꾸러미는 각각 최대 한 키트에만 들어간다. 만들 수 있는 유효한 키트 수의 최댓값을 구하라. 총 인분 수까지 최대로 만들 필요는 없다.

정리하면, $i$번 재료에서 $Q_i$ g짜리 꾸러미를 하나씩 골라 만든 키트에 라벨 $S$를 붙였을 때, $S$가 양의 정수이고 모든 $i$에 대해 $0.9 \times S \times R_i \le Q_i \le 1.1 \times S \times R_i$이면 그 키트는 유효하다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 재료의 수 $N$과 재료마다 있는 꾸러미의 수 $P$가 주어진다.
• 둘째 줄에 $N$개의 정수 $R_i$가 주어진다. $i$번째 값은 $i$번 재료가 한 인분에 몇 그램 필요한지를 뜻한다.
• 이어지는 $N$개의 줄에 각각 $P$개의 정수가 주어진다. $i$번째 줄의 $j$번째 값 $Q_{ij}$는 $i$번 재료의 $j$번째 꾸러미에 들어 있는 양이며, 단위는 그램이다.

제한

• $1 \le T \le 100$
• $1 \le N \le 3$
• $1 \le P \le 8$
• $1 \le R_i \le 10^6$
• $1 \le Q_{ij} \le 10^6$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 만들 수 있는 키트 수의 최댓값이다.

예제의 첫 두 테스트 케이스는 문제에서 설명한 상황이다.

세 번째 케이스에서는 1번 재료의 450 g 꾸러미와 2번 재료의 1100 g 꾸러미를 묶어 10인분 라벨을 붙일 수 있다. 10인분에는 1번 재료가 500 g 필요한데 450 g은 그 90%이고, 2번 재료가 1000 g 필요한데 1100 g은 그 110%다. 이 키트를 만들고 나면 남은 449 g 꾸러미와 1101 g 꾸러미에는 어떤 라벨도 붙일 수 없으므로, 만들 수 있는 키트는 이 하나뿐이다.

네 번째 케이스에서는 키트를 하나도 만들 수 없다. 요리법은 재료마다 필요한 양을 순서대로 정해 두었고, 재료끼리 바꿔 쓸 수 없다.

다섯 번째 케이스의 요리법은 재료가 하나다. 1인분에는 11 g을 넘게 쓸 수 없고, 2인분에는 18 g보다 적게 쓸 수 없다. 키트는 세 개까지 만들 수 있다. 11 g 꾸러미로 1인분 키트를 두 개, 18 g 꾸러미로 2인분 키트를 하나 만들면 된다.

여섯 번째 케이스에서는 키트 세 개가 유효하다. (700 g, 800 g, 900 g)에 10인분 라벨을 붙이고, (1500 g, 1600 g, 1700 g)과 (1260 g, 1440 g, 1620 g)에 각각 20인분 라벨을 붙인다. 마지막 키트에는 17인분, 18인분, 19인분 라벨을 붙여도 된다. 키트가 유효하기만 하면 라벨에 적은 인분 수는 답에 영향을 주지 않는다.