IP Address Summarization (Large)

An IP (Internet Protocol) address is a number assigned to each device on the Internet. Most devices today use the fourth version of this protocol (IPv4). An IPv4 address is a 32-bit string. IPv4 addresses are normally written in dot-decimal notation: four decimal numbers called octets, each from 0 to 255 inclusive, joined by dots, for example 172.16.254.1. Each octet stands for 8 bits (one byte) of the address. Reading the string from the most significant bit, the first 8 bits form the first octet, the next 8 bits form the second octet, and so on.

An IP subnet address represents a group of devices that belong to the same network. A subnet address is written as an IP address, then a slash, then a prefix length from 0 to 32. A subnet address with prefix length P stands for every IP address whose first P bits match the first P bits of the given address. For example, 10.8.0.0/9 represents the $2^{23}$ addresses whose first 9 bits are 000010100 (the first nine bits of 10.8.0.0), that is, 10.0.0.0 through 10.127.255.255. Note that 10.8.0.0/9 and 10.0.0.0/9 name the same subnet, because those addresses start with the same nine bits, and so does any other address inside that subnet.

A subnet is normalized if the address bits after the prefix are all zeroes. For example, 10.8.1.0/24 and 10.8.1.2/24 name the same subnet, but 10.8.1.0/24 is the normalized one. The normalization of 255.255.255.255/13 is 255.248.0.0/13.

You are given a list of subnet addresses. Output the shortest ordered list of subnets such that every listed address is normalized, and an address belongs to some subnet in the input if and only if it belongs to some subnet in the output.

The first line holds the number of test cases, T. T test cases follow. Each begins with one line holding an integer N, the number of subnets, followed by N more lines, each holding one subnet address. Each subnet address has the form A.B.C.D/P, where A, B, C, and D are integers from 0 to 255 inclusive, and P is an integer from 0 to 32 inclusive. No integer other than 0 itself has a leading zero.

Limits

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 10000

For each test case, output one line holding "Case #x:", where x is the test case number starting from 1. Then output the list of subnet addresses that meets the conditions above, one per line. These addresses must be normalized and must be ordered. An address X comes before an address Y if X's first integer is smaller than Y's first integer, or if the two first integers are equal and X's second integer is smaller than Y's second integer, and so on for the remaining integers.

The conditions of the problem guarantee that each test case has exactly one answer.