주스 배합

파티를 열면서 사과 주스, 바나나 주스, 당근 주스 세 가지를 섞어 음료 한 통을 만든다. 세 주스를 각각 주스 A, 주스 B, 주스 C라고 하자.

음료에서 세 주스가 각각 차지하는 비율을 정해야 한다. 비율은 만분율 정수로 나타내고, 세 값의 합은 정확히 $10000$이다.

손님마다 주스별로 원하는 최소 비율이 정해져 있다. 음료에 들어간 세 주스의 비율이 모두 그 손님의 최소 비율 이상일 때만 그 손님은 음료를 마음에 들어 한다.

비율을 잘 정해서 음료를 마음에 들어 하는 손님 수를 최대로 만들고, 그 최댓값을 구하라.

첫 줄에 테스트 케이스의 개수 T가 주어진다.

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

• 첫 줄에 파티에 오는 손님 수 N이 주어진다.
• 다음 N개의 줄에 손님 한 명씩의 정보가 "A B C" 형식으로 공백을 두고 주어진다. A, B, C는 그 손님이 주스별로 원하는 최소 비율을 만분율로 나타낸 정수이고, $0 \le A, B, C \le 10000$, $A + B + C \le 10000$을 만족한다.

제한

• $1 \le T \le 12$
• $1 \le N \le 5000$

테스트 케이스마다 한 줄씩, 입력에 주어진 순서대로 "Case #X: Y" 형식으로 출력한다. X는 $1$부터 시작하는 테스트 케이스 번호이고, Y는 음료를 마음에 들어 하는 손님 수의 최댓값이다.

첫 번째 예제의 첫 번째 테스트 케이스에서는 세 손님이 각각 서로 다른 주스 하나만으로 음료를 만들기를 원하므로, 한 명만 만족시킬 수 있다.

두 번째 테스트 케이스에서는 세 손님 중 어느 두 명이든 함께 만족시킬 수 있다.

세 번째 테스트 케이스에서는 세 주스의 비율을 $3334$, $3333$, $3333$으로 정하면 다섯 손님 모두가 음료를 마음에 들어 한다.