새로운 원소: 파트 1

이 문제의 첫 두 문단(이 문단은 세지 않음)은 "New Elements: Part 2"의 첫 두 문단과 동일하다. 그 외에는 두 문제를 서로 독립적으로 풀 수 있으며, 한 문제를 읽거나 풀기 위해 다른 문제를 읽거나 풀 필요는 없다.

Muriel은 자신이 Codium과 Jamarium이라고 이름 붙인 두 새로운 원소를 발견하는 과정에 있다. 아직 이들을 분리해 내지는 못했지만, 간접적인 방법으로 원자량과 같은 몇 가지 중요한 성질을 조사하기 시작하고 싶어 한다. Muriel은 Codium의 단일 동위원소와 Jamarium의 단일 동위원소를 다루고 있으므로, 이들의 원자량은 엄격히 양의 정수이다.

Muriel은 서로 다른 N개의 분자를 만드는 데 성공했다. 각 분자는 Codium 원자를 하나 이상, Jamarium 원자를 하나 이상 포함하며 다른 원소는 포함하지 않는다. 각 분자에 대해, 그녀는 각 원소의 원자가 몇 개 들어 있는지 알고 있다. 분자의 분자량은 그 분자가 포함하는 모든 원자의 원자량을 합한 값이다.

분자들의 정확한 분자량과 두 원소의 원자량을 알아내기 위한 첫 단계로, Muriel은 분자들을 분자량이 엄격히 증가하도록 정렬하려 한다. 그 작업의 난이도를 평가하기 위해, 현재 가진 정보만 고려했을 때 유효한 순서가 몇 개인지 알고 싶어 한다. Codium과 Jamarium의 원자량에 어떤 값을 부여했을 때 해당 순서에서 분자량이 엄격히 증가한다면, 그 분자 순서는 유효하다고 간주한다.

예를 들어 각 분자는 그 안에 포함된 Codium 원자의 수와 Jamarium 원자의 수로 이루어진 순서쌍으로 나타낸다. Muriel에게 (1, 1), (2, 1), (1, 2)로 나타낸 3개의 분자가 있다면, 분자량이 엄격히 증가할 수 있는 순서는 (1, 1), (1, 2), (2, 1)와 (1, 1), (2, 1), (1, 2)의 두 가지이다. 첫 번째 순서는 두 원소 중 Codium이 더 무거워지는 어떤 원자량 배정에서도 유효하고, 두 번째 순서는 Jamarium이 더 무거워지는 어떤 배정에서도 유효하다. 남은 유일한 경우는 Codium과 Jamarium의 원자량이 같은 경우인데, 이때는 (1, 2)와 (2, 1)의 분자량이 같으므로 이 상황에서는 엄격히 증가하는 순서를 만들 수 없다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $C_{i}$ ≤ $10^{9}$, 모든 i에 대해. 1 ≤ $J_{i}$ ≤ $10^{9}$, 모든 i에 대해. 모든 i ≠ j에 대해 ($C_{i}$, $J_{i}$) ≠ ($C_{j}$, $J_{j}$). (모든 분자는 서로 다르다.)

테스트 세트 1 (공개)

2 ≤ N ≤ 6.

테스트 세트 2 (비공개)

2 ≤ N ≤ 300.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 테스트 케이스의 첫 번째 줄에는 분자의 수를 나타내는 정수 N 하나가 주어진다. 이어지는 N개의 각 줄은 서로 다른 분자 하나를 설명하며, 두 정수 $C_{i}$와 $J_{i}$는 각각 i번째 분자에 있는 Codium 원자와 Jamarium 원자의 수를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 정의한 유효한 순서의 총개수이다.

예제 케이스 #1은 문제 설명에 해설되어 있다.

예제 케이스 #2에서 유효한 두 순서는 (1, 2), (2, 1), (2, 4), (4, 2)와 (2, 1), (1, 2), (4, 2), (2, 4)이다. (1, 2), (2, 1), (4, 2), (2, 4) 순서는 유효하지 않음에 유의하라. (1, 2)가 (2, 1)보다 엄격히 가볍다면, (1, 2)보다 정확히 두 배 무거운 (2, 4)는 (2, 1)보다 정확히 두 배 무거운 (4, 2)보다 반드시 엄격히 가벼워야 하기 때문이다.