무늬와 그림

천에는 당근과 박쥐를 번갈아 배치한 것과 같이 반복되는 무늬가 그려져 있는 경우가 많다.

위 예시의 당근처럼, 하나의 그림은 천 위에서 정해진 넓이(제곱인치)를 차지한다. 또한 두 종류 이상의 그림이 있는 천에서는 그림들이 간단한 정수비로 나타난다. 예를 들어 당근 3개마다 박쥐 2개가 있는 식이다. 주어진 비율대로 각 그림이 한 번씩 나타난 것을 한 세트(full set)라고 한다.

천은 제곱야드 단위로 판매된다(1야드는 36인치이다). 그림의 종류와 각각의 넓이, 그리고 등장 비율이 주어졌을 때, 무늬가 있는 천 1제곱야드, 2제곱야드, 3제곱야드 위에 나타날 수 있는 세트의 최대 개수는 각각 얼마인가?

(이 최댓값은 그림의 모양과 배치를 완전히 자유롭게 정할 수 있다고 가정한 값이며, 세 가지 길이에서 서로 다르게 배치해도 된다. 실제 배치 방법은 이 문제에서 고려하지 않는다.)

입력의 첫 줄에는 데이터 집합의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어진다. 각 데이터 집합은 다음과 같이 구성된다.

• 한 무늬에 포함된 그림의 종류 수를 나타내는 정수 $I$ ($1 \le I \le 10$)가 한 줄에 주어진다.
• 이어서 $I$개의 줄이 주어지며, 각 줄에는 공백으로 구분된 두 정수 $S$, $R$ ($1 \le S \le 1000$; $1 \le R \le 100$)이 주어진다. $S$는 해당 그림이 차지하는 넓이(제곱인치)이고, $R$은 한 세트에 포함되는 그 그림의 개수이다.

각 데이터 집합에 대해 A B C를 출력한다. $A$는 천 1제곱야드에 나타날 수 있는 세트의 최대 개수, $B$는 2제곱야드에 나타날 수 있는 세트의 최대 개수, $C$는 3제곱야드에 나타날 수 있는 세트의 최대 개수이다.