IP 주소 요약

IP (인터넷 프로토콜) 주소는 인터넷상의 각 장치에 할당되는 숫자이다. 현재 대부분의 장치는 이 프로토콜의 버전 사(IPv4)를 사용한다. IPv4 주소는 32비트 문자열이다. IPv4 주소는 일반적으로 옥텟이라고 하는 네 개의 십진수로 구성된 점-십진 표기법으로 나타내며, 각 옥텟의 범위는 0부터 255까지(양 끝 포함)이고 점으로 구분한다. 예를 들면 172.16.254.1이다. 각 옥텟은 주소의 8비트 묶음(한 바이트)을 나타낸다. 문자열의 처음 8비트(최상위 비트부터 시작하는 부호 없는 정수로 해석)는 첫 번째 옥텟을 이루고, 다음 8비트는 두 번째 옥텟을 이루며, 이런 식으로 이어진다.

IP 서브넷 주소는 같은 네트워크에 속한 장치들의 집합을 나타내는 데 사용된다. IP 서브넷 주소는 IP 주소 뒤에 슬래시와 0부터 32까지 범위의 접두사 길이를 붙인 형식으로 표현한다. 서브넷 주소는 주어진 주소의 처음 P비트가 같은 모든 IP 주소를 나타내며, 여기서 P는 접두사 길이이다. 예를 들어 10.8.0.0/9은 모두 처음 9비트가 000010100(10.8.0.0의 처음 아홉 비트)인 $2^{23}$개의 주소, 즉 10.0.0.0부터 10.127.255.255까지를 나타낸다. 10.8.0.0/9와, 예를 들어 10.0.0.0/9(또는 서브넷 내의 다른 어떤 주소든)은 같은 서브넷을 가리키는 동등한 방법이라는 점에 유의하라. 해당 주소들이 동일한 처음 아홉 비트로 시작하기 때문이다.

접두사 이외의 주소 비트가 모두 영이면 서브넷은 정규화되어 있다. 예를 들어 10.8.1.0/24와 10.8.1.2/24는 같은 서브넷을 나타내지만, 10.8.1.0/24는 정규화되어 있다. 255.255.255.255/13를 정규화한 것은 255.248.0.0/13이다.

서브넷 주소의 목록이 주어지며, 모든 주소가 정규화되어 있고 어떤 주소가 입력의 어떤 서브넷에 속할 때, 그리고 그럴 때에만 출력의 어떤 서브넷에 속하도록 하는 가장 짧은 순서 있는 서브넷 목록을 출력해야 한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 50.

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

시간 제한: 30초. 1 ≤ N ≤ 10.

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

시간 제한: 60초. 1 ≤ N ≤ 10000.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 서브넷의 수를 나타내는 정수 N이 있는 한 줄로 시작하며, 그 뒤에 각각 서브넷 주소 하나가 있는 N개의 줄이 더 주어진다. 각 서브넷 주소의 형식은 A.B.C.D/P이며, A, B, C, D는 양 끝을 포함하여 0부터 255까지의 정수이고 P는 양 끝을 포함하여 0부터 32까지의 정수이다. 어떤 정수도(0은 제외) 앞에 불필요한 영이 붙지 않는다.

각 테스트 케이스마다 "Case #x:"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이다. 그런 다음 위에서 설명한 조건을 충족하는 서브넷 주소 목록을 한 줄에 하나씩 출력한다. 이 주소들은 정규화되어 있어야 하며 순서대로 정렬되어야 한다. 주소 X의 첫 번째 정수가 주소 Y의 첫 번째 정수보다 작거나, X와 Y의 첫 번째 정수가 같지만 X의 두 번째 정수가 더 작거나, 이후에도 같은 방식으로 비교했을 때 더 작다면 X가 Y보다 앞에 온다.

문제의 요구 사항에 따라 각 테스트 케이스의 답이 단 하나로 유일하게 정해진다는 점에 유의하라.