IP Address Summarization

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

A subnet address describes a group of devices that belong to the same network. It is written as an IP address, then a slash, then a prefix length P from 0 to 32. The subnet contains every IP address whose first P bits equal the first P bits of the given address. For example, 10.8.0.0/9 contains $2^{23}$ addresses, all of which start with the nine bits 000010100, that is, every address from 10.0.0.0 to 10.127.255.255. Writing 10.0.0.0/9, or any other address inside that subnet with the same prefix length, names the same subnet, because those addresses share their first nine bits.

A subnet is normalized when every bit of the address after the prefix is zero. For example, 10.8.1.0/24 and 10.8.1.2/24 are the same subnet, and 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 subnet you list is normalized, and an address belongs to some subnet of the input if and only if it belongs to some subnet of the output.

The first line of the input gives 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. Apart from 0 itself, no integer has leading zeroes.

Limits

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

For each test case, output one line containing Case #x:, where x is the test case number starting from 1. Then output the subnet addresses that meet 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 X and Y have the same first integer and X's second integer is smaller than Y's second integer. The third and fourth integers are compared the same way.

The requirements of the problem guarantee a single answer for each test case.