주스

당신은 파티를 열고 있다. 준비 과정에서 Apple, Banana, Carrot이라는 서로 다른 세 종류의 과일 주스를 섞어 음료를 만들고 있다. 이 주스들을 A, B, C라고 하자.

파티 참석자 중 가능한 한 많은 사람이 이 음료를 좋아하도록, 각 주스 종류가 음료에서 차지해야 할 비율을 정하려고 한다.

각 사람에게는 음료에 들어 있기를 원하는 3 주스 각각의 최소 비율이 있다. 음료에 들어 있는 3 주스 각각의 비율이 그 주스에 대해 그 사람이 요구하는 최소 비율보다 크거나 같을 때에만 그 사람은 음료를 좋아한다.

만족시킬 수 있는 사람 수의 최댓값을 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 12

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 5000

• 입력 파일의 테스트 케이스 수를 나타내는 정수 T가 한 줄에 주어진다.

각 테스트 케이스에는 다음이 주어진다.

• 파티에 참석하는 사람 수를 나타내는 정수 N이 한 줄에 주어진다.

• 각 사람마다 한 줄씩 총 N개의 줄이 주어지며, 각 줄에는 음료에 들어 있기를 원하는 각 주스의 최소 비율을 나타내는, 공백으로 구분된 세 수 "A B C"가 주어진다. A, B, C는 0 이상 10000 이하인 정수이며, 만분율로 비율을 나타낸다. A + B + C ≤ 10000.

• 입력 파일에 등장한 순서대로 각 테스트 케이스마다 한 줄씩, 총 T개의 줄을 출력한다. 각 줄에는 문자열 "Case #X: Y"을 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 당신의 음료를 좋아할 사람 수의 최댓값이다.

첫 번째 경우에는 각 주스마다 음료가 전부 그 주스로 만들어지기를 원하는 사람이 한 명씩 있다! 명백히 그중 한 명만 만족시킬 수 있다.

두 번째 경우에는 세 선호 조건 중 어느 두 개든 만족시킬 수 있다.

세 번째 경우에는 각 주스를 동일하게 삼분의 일씩 사용해 음료를 만들면 다섯 사람 모두가 음료를 좋아한다.