IP 주소 요약

IP(Internet Protocol) 주소는 인터넷에 연결된 각 장치에 부여하는 번호다. 지금도 대부분의 장치는 이 프로토콜의 네 번째 판인 IPv4를 쓴다. IPv4 주소는 32비트 문자열이고, 보통 점으로 구분한 10진 표기로 적는다. 이 표기는 옥텟이라고 부르는 0 이상 255 이하의 10진수 네 개를 점으로 이어 쓴 것으로, 예를 들면 172.16.254.1이다. 옥텟 하나는 주소의 8비트(1바이트)를 나타낸다. 32비트를 최상위 비트부터 읽어 앞의 8비트가 첫 번째 옥텟, 그다음 8비트가 두 번째 옥텟이 되고, 나머지도 같은 방식이다.

서브넷 주소는 같은 네트워크에 속한 장치 무리를 나타낸다. 서브넷 주소는 IP 주소 뒤에 빗금과 0 이상 32 이하의 접두사 길이 P를 붙인 형태로 적는다. 서브넷은 주어진 주소와 앞 P비트가 같은 모든 IP 주소를 뜻한다. 예를 들어 10.8.0.0/9는 앞 9비트가 000010100인 주소 $2^{23}$개, 곧 10.0.0.0부터 10.127.255.255까지를 나타낸다. 10.0.0.0/9처럼 같은 서브넷 안의 다른 주소를 적어도 앞 9비트가 같으므로 같은 서브넷을 가리킨다.

접두사 뒤의 비트가 모두 0인 서브넷을 정규화된 서브넷이라고 한다. 예를 들어 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이다.

서브넷 주소 목록이 주어진다. 나열한 서브넷이 모두 정규화된 형태이고, 어떤 주소가 입력의 어떤 서브넷에 속하는 것과 출력의 어떤 서브넷에 속하는 것이 서로 같은 조건이 되는, 가장 짧은 순서 있는 서브넷 목록을 출력하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 서브넷의 개수 N이 주어지고, 다음 N개 줄에 서브넷 주소가 한 줄에 하나씩 주어진다. 서브넷 주소의 형식은 A.B.C.D/P이고, A, B, C, D는 0 이상 255 이하의 정수, P는 0 이상 32 이하의 정수다. 0을 빼면 어떤 정수에도 앞자리 0은 붙지 않는다.

제한

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 10

각 테스트 케이스마다 먼저 Case #x:를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 그 뒤에 위 조건을 만족하는 서브넷 주소를 한 줄에 하나씩 출력한다. 출력하는 주소는 모두 정규화된 형태여야 하고, 정해진 순서대로 나열해야 한다. 주소 X의 첫 번째 정수가 주소 Y의 첫 번째 정수보다 작거나, 두 주소의 첫 번째 정수가 같으면서 X의 두 번째 정수가 Y의 두 번째 정수보다 작으면 X가 Y보다 앞에 온다. 세 번째 정수와 네 번째 정수도 같은 방식으로 비교한다.

문제의 조건에 따라 각 테스트 케이스의 답은 하나로 정해진다.