충전 대혼란

농부 Shota에게 문제가 생겼다. 그는 막 새로 지은 농가로 이사했지만, 모든 기기에 맞게 콘센트가 올바르게 설정되어 있지 않다는 사실을 알게 되었다. 현대적인 농부인 Shota는 많은 스마트폰과 노트북을 가지고 있으며, 자신이 가장 아끼는 소 Wagyu가 사용할 태블릿까지 가지고 있다. 그가 가진 서로 다른 기기는 모두 N개이다.

이 기기들은 사양이 서로 다르고 여러 회사에서 제조되었으므로, 충전하는 데 각각 서로 다른 전류가 필요하다. 마찬가지로 집 안의 각 콘센트는 특정한 전류를 출력한다. 전류는 길이가 L인 0과 1로 이루어진 문자열로 나타낼 수 있다.

Shota는 자신의 N개 기기를 모두 동시에 충전할 수 있기를 바란다. 공교롭게도 새집에는 정확히 N개의 콘센트가 있다. 콘센트의 전류를 설정하기 위해 L개의 스위치가 있는 주 제어판이 마련되어 있다. $i^{th}$ 스위치는 집 안의 모든 콘센트에서 나오는 전류의 $i^{th}$ 비트를 뒤집는다. 예를 들어 콘센트에서 나오는 전류가 다음과 같다고 하자.

Outlet 0: 10
Outlet 1: 01
Outlet 2: 11

이때 두 번째 스위치를 뒤집으면 전류가 다음과 같이 재설정된다.

Outlet 0: 11
Outlet 1: 00
Outlet 2: 10

Shota에게 충전하는 데 "11" 전류가 필요한 스마트폰, "10" 전류가 필요한 태블릿, "00" 전류가 필요한 노트북이 있다면, 두 번째 스위치를 뒤집었을 때 그는 매우 기뻐할 것이다!

Misaki는 이 문제를 해결하도록 Shota를 돕기 위해 고용되었다. 그녀는 집 안의 콘센트에서 나오는 전류를 측정하고, 그 전류가 모두 서로 다르다는 것을 알아냈다. Shota가 자신의 모든 기기를 동시에 충전할 수 있는지 판별하고, 가능하다면 뒤집어야 하는 스위치의 최소 개수를 구하라. 스위치는 크고 무거우며 Misaki는 필요한 것보다 더 많이 뒤집고 싶지 않기 때문이다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 처음에 같은 전류를 내보내는 두 콘센트는 없다. 같은 전류를 요구하는 두 기기는 없다.

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 10. 2 ≤ L ≤ 10.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ 150. 10 ≤ L ≤ 40.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫 번째 줄에는 공백으로 구분된 두 정수 N과 L이 주어진다. 두 번째 줄에는 콘센트의 초기 전류를 나타내는 길이 L의 문자열 N개가 공백으로 구분되어 주어진다. 세 번째 줄에도 Shota의 기기들이 요구하는 전류를 나타내는 길이 L의 문자열 N개가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 Shota가 자신의 모든 기기를 충전할 수 있도록 하기 위해 뒤집어야 하는 스위치의 최소 개수이다. 불가능하다면 y는 문자열 "NOT POSSIBLE"이어야 한다(따옴표 제외). 채점기는 대소문자를 구분하지 않지만 다른 면에서는 엄격하다는 점에 유의하라. 따라서 "not possible"도 정답으로 판정되지만, 철자가 하나라도 틀리면 오답으로 판정된다. 문자열 NOT POSSIBLE을 코드에 복사하여 붙여 넣는 것을 권장한다.

설명

첫 번째 예제 테스트 케이스에서 Misaki는 두 번째 스위치를 한 번 뒤집을 수 있다. 그러면 콘센트에서 나오는 전류는 다음과 같이 된다.

그런 다음 Shota는 콘센트 0을 사용해 기기 1를 충전하고, 콘센트 1을 사용해 기기 2를 충전하며, 콘센트 2을 사용해 기기 0를 충전할 수 있다. 이것은 뒤집어야 하는 스위치의 개수가 최소인 해이기도 하다.