Fixing Codes

A binary string is a string over the alphabet $\{0, 1\}$. A code is a multiset of binary strings (the same string may appear any number of times). A code is a fixed code if none of its strings is a prefix of another string in it.

A code $A = \{a_1, a_2, \ldots, a_n\}$ is extended to a code $B = \{b_1, b_2, \ldots, b_n\}$ if $a_i$ is a prefix of $b_i$ for every $1 \le i \le n$. The cost of this extension is $\sum_{i=1}^{n} (|b_i| - |a_i|)$, where $|x|$ is the length (number of characters) of string $x$.

You are given a fixed code $C$ and a new binary string $s$. Find the minimum cost needed to extend $C \cup \{s\}$ into a fixed code. In other words, append the fewest possible bits to zero or more of the strings in $C \cup \{s\}$ so that the whole collection becomes a fixed code.

The first line contains an integer $t$ ($1 \le t \le 20$), the number of test cases. Each of the next $t$ lines contains one or more binary strings separated by spaces. Each line has at most 41 strings, and every string has length at most 40. On each line the last string is the new incoming string $s$, and the remaining strings form the fixed code $C$ for that test case.

For each test case, print the minimum cost to extend $C \cup \{s\}$ into a fixed code on its own line.