새로운 원소: Part 1

이 문제와 "New Elements: Part 2"의 처음 두 문단(이 문단은 제외)은 같다. 그 밖의 부분은 서로 독립적이어서, 한 문제를 읽거나 풀기 위해 다른 문제를 읽거나 풀 필요는 없다.

뮤리엘은 Codium과 Jamarium이라고 이름 붙인 두 새로운 원소를 발견하는 중이다. 아직 두 원소를 분리하지는 못했지만, 원자량 같은 성질을 간접적인 방법으로 조사하려고 한다. 뮤리엘은 Codium의 동위원소 하나와 Jamarium의 동위원소 하나만 다루므로, 두 원소의 원자량은 모두 양의 정수다.

뮤리엘은 서로 다른 분자 $N$개를 만들었다. 각 분자에는 Codium 원자가 하나 이상, Jamarium 원자가 하나 이상 들어 있으며, 다른 원소는 없다. 각 분자에 들어 있는 원소별 원자 수는 알고 있다. 분자량은 분자에 들어 있는 모든 원자의 원자량을 더한 값이다.

정확한 분자량과 원자량을 구하는 첫 단계로, 뮤리엘은 분자를 분자량이 엄격하게 증가하는 순서로 정렬하려고 한다. 이 작업이 얼마나 어려운지 알아보려고, 지금 가진 정보만으로 유효한 순서가 몇 가지인지 알고 싶다. 순서가 유효하다는 것은 Codium과 Jamarium의 원자량이 어떤 값으로 주어졌을 때, 그 순서대로 분자량이 엄격하게 증가한다는 뜻이다.

예를 들어 각 분자를 Codium과 Jamarium 원자 수의 쌍으로 나타내자. 분자가 (1, 1), (2, 1), (1, 2) 세 개라면 엄격하게 증가하는 순서는 두 가지다. (1, 1), (1, 2), (2, 1)과 (1, 1), (2, 1), (1, 2)이다. 첫 번째 순서는 Codium이 Jamarium보다 무거울 때 유효하고, 두 번째 순서는 Jamarium이 더 무거울 때 유효하다. 두 원소의 원자량이 같으면 (1, 2)와 (2, 1)의 분자량이 같으므로 엄격하게 증가하는 순서가 없다.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 분자의 개수 N이 주어진다. 다음 N개의 줄에는 i번째 분자에 들어 있는 Codium 원자 수 $C_i$와 Jamarium 원자 수 $J_i$가 주어진다.

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

• $1 \le T \le 100$.
• 모든 $i$에 대해 $1 \le C_i \le 10^9$.
• 모든 $i$에 대해 $1 \le J_i \le 10^9$.
• $i \ne j$이면 $(C_i, J_i) \ne (C_j, J_j)$이다. 모든 분자는 서로 다르다.

샘플 케이스 #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)보다 엄격하게 가벼워야 하기 때문이다.