밀크티

중국의 밀크티는 매우 맛있다. 밀크티 주문을 맞춤 설정할 때는 "얼음 있음"/"얼음 없음", "설탕 있음"/"설탕 없음", "타피오카 펄 있음"/"타피오카 펄 없음", "푸딩 있음"/"푸딩 없음" 등 많은 이진 선택지("둘 중 하나")가 있다. 고객의 밀크티 선호는 이진 문자열로 나타낼 수 있다. 예를 들어 위의 네 가지 속성을 주어진 순서대로 사용할 때, 문자열 1100은 "얼음 있음, 설탕 있음, 타피오카 펄 없음, 푸딩 없음"을 의미한다.

오늘 Shakti는 P개의 이진 선택지를 제공하는 가게에서 N명의 친구 각각에게 밀크티를 사 주는 일을 맡았다. 하지만 모두의 선호를 모은 뒤 주문이 너무 복잡해지고 있다는 것을 깨달은 Shakti는 모두에게 같은 종류의 밀크티를 사 주기로 했다. Shakti는 각 친구가 충족되지 않은 선호 하나마다 한 번씩 불평한다는 것을 알고 있다. 예를 들어 친구 중 두 명이 각각 101과 010 종류를 선호하고 Shakti가 001 종류를 선택하면, 첫 번째 친구는 한 번, 두 번째 친구는 두 번 불평하여 총 세 번의 불평이 발생한다.

또한 가게에서 만들어 주지 않는 서로 다른 금지된 밀크티 종류가 M개 있으며, Shakti는 이 금지된 종류 중 어느 것도 선택할 수 없다.

Shakti가 받을 수 있는 불평 횟수의 최솟값은 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 케이스당 30초. 메모리 제한: 1 GB. 금지된 모든 밀크티 종류는 서로 다르다.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 10. 1 ≤ M ≤ min(10, $2^{P}$ - 1). 1 ≤ P ≤ 10.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 100. 1 ≤ M ≤ min(100, $2^{P}$ - 1). 1 ≤ P ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 정수 N, M, P를 포함하는 한 줄로 시작하며, 이 줄에는 3개의 정수가 있다. 그다음에는 각각 이진 문자열 하나를 포함하는 N개의 줄이 추가로 주어지며, 이 문자열들은 N명 친구의 선호를 나타낸다. 마지막으로 각각 이진 문자열 하나를 포함하는 M개의 줄이 추가로 주어지며, 이 문자열들은 가게에서 만들어 주지 않는 금지된 밀크티 종류를 나타낸다. 이진 문자열은 0 및/또는 1 문자로만 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 위에서 설명한 규칙에 따라 Shakti가 받을 수 있는 불평 횟수의 최솟값이다.

예제 케이스 #1에는 친구가 3명 있으며, 이들은 1100, 1010, 0000 종류의 밀크티를 원한다. Shakti가 1000 종류를 선택할 수 있다면 각 친구가 한 번씩 불평하여 총 3번의 불평이 발생한다. 하지만 1000 종류는 가게에서 제공되지 않는다. 따라서 이러한 제약 조건에서 최적의 해는 1100 종류를 선택하는 것이다. 그러면 친구들은 각각 0, 2, 2번 불평하여 총 4번의 불평이 발생한다.

예제 케이스 #2에서 Shakti의 최선의 선택은 1110 종류를 고르는 것이다. 각 친구가 한 번씩 불평하여 총 2번의 불평이 발생한다. 서로 다른 친구들이 같은 선호를 가질 수도 있다는 점에 유의한다. 또한 작은 데이터 세트와 큰 데이터 세트의 제한은 금지되지 않은 밀크티 종류가 항상 적어도 하나 존재함을 보장한다.