코드 고치기

이진 문자열은 집합 ${0, 1}$의 문자로만 이루어진 문자열입니다. 코드(code) 는 이진 문자열의 중복집합(multiset)으로, 같은 문자열이 여러 번 나타날 수 있습니다. 어떤 코드에 속한 그 어떤 문자열도 다른 문자열의 접두사(prefix)가 아닐 때, 그 코드를 고정 코드(fixed code) 라고 부릅니다.

코드 $A = {a_1, a_2, \ldots, a_n}$가 코드 $B = {b_1, b_2, \ldots, b_n}$로 확장(extend) 된다는 것은, 모든 $1 \le i \le n$에 대해 $a_i$가 $b_i$의 접두사임을 뜻합니다. 이때 확장의 비용은 $\sum_{i=1}^{n} (|b_i| - |a_i|)$이며, $|x|$는 문자열 $x$의 길이(문자 개수)입니다.

고정 코드 $C$와 새로운 이진 문자열 $s$가 주어집니다. $C \cup {s}$를 고정 코드로 확장하는 데 필요한 최소 비용을 구하세요. 다시 말해, $C \cup {s}$에 속한 문자열 중 0개 이상에 비트를 덧붙여(append) 전체가 고정 코드가 되도록 할 때, 덧붙이는 비트 수의 최솟값을 구하면 됩니다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 20$)가 주어집니다. 이어지는 $t$개의 줄에는 각각 공백으로 구분된 이진 문자열이 1개 이상 주어집니다. 한 줄에 등장하는 문자열은 최대 41개이며, 각 문자열의 길이는 최대 40입니다. 각 줄의 마지막 문자열은 새로 들어오는 문자열 $s$이고, 나머지 문자열들이 그 테스트 케이스의 고정 코드 $C$를 이룹니다.

각 테스트 케이스마다 $C \cup {s}$를 고정 코드로 확장하는 최소 비용을 한 줄에 하나씩 출력합니다.