

Multibit TrieTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1160 Accepted Submission(s): 537 Problem Description IP lookup is one of the key functions of routers for packets forwarding and classifying. Generally, IP lookup can be simplified as a Longest Prefix Matching (LPM) problem. That's to find the longest prefix in the Forwarding Information Base (FIB) that matches the input packet's destination address, and then output the corresponding Next Hop information. Triebased solution is the most wildly used one to solve LPM. As shown in Fig.1(b), an unibit trie is just a binary tree. Processing LPM on it needs only traversing it from the root to some leaf, according to the input packet's destination address. The longest prefix along this traversing path is the matched one. In order to reduce the memory accesses for one lookup, we can compress some consecutively levels of the Unibit Trie into one level, transforming the Unibit Trie into a Multibit Trie. For example, suppose the strides array is {3, 2, 1, 1}, then we can transform the Unibit Trie shown in Fig.1(b) into a Multibit Trie as shown in Fig.1(c). During the transforming process, some prefixes must be expanded. Such as 11(P2), since the first stride is 3, it should be expanded to 110(P2) and 111(P2). But 110(P5) is already exist in the FIB, so we only store the longer one 110(P5). Multibit Trie can obviously reduce the tree level, but the problem is how to build a Multibit Trie with the minimal memory consumption (the number of memory units). As shown in Fig.1, the Unibit Trie has 23 nodes and consumes 46 memory units in total, while the Multibit Trie has 12 nodes and consumes 38 memory units in total. Input The first line is an integer T, which is the number of testing cases. The first line of each case contains one integer L, which means the number of levels in the Unibit Trie. Following L lines indicate the nodes in each level of the Unibit Trie. Since only 64 bits of an IPv6 address is used for forwarding, a Unibit Trie has maximal 64 levels. Moreover, we suppose that the stride for each level of a Multibit Trie must be less than or equal to 20. Output Output the minimal possible memory units consumed by the corresponding Multibit Trie. Sample Input
Sample Output
Source  
