충전 대혼란 (라지)

농부 쇼타가 새로 지은 농가로 이사했는데, 콘센트가 자기 기기에 맞게 설정되어 있지 않다. 쇼타는 스마트폰과 노트북을 여러 대 쓰고, 아끼는 소 와규가 쓰는 태블릿도 있다. 기기는 모두 $N$개다.

기기마다 사양과 제조사가 달라서 충전에 필요한 전류가 서로 다르다. 콘센트도 저마다 정해진 전류를 내보낸다. 전류 하나는 0과 1로 이루어진 길이 $L$의 문자열로 나타낸다.

쇼타는 기기 $N$개를 동시에 충전하려고 한다. 마침 새 집에는 콘센트도 정확히 $N$개 있다. 콘센트가 내보내는 전류는 스위치가 $L$개 달린 제어판으로 조절한다. $i$번 스위치를 내리면 집 안 모든 콘센트가 내보내는 전류의 $i$번째 비트가 뒤집힌다.

예를 들어 콘센트 세 개가 각각 10, 01, 11을 내보내고 있을 때 두 번째 스위치를 내리면 전류는 11, 00, 10으로 바뀐다. 충전에 11이 필요한 스마트폰, 10이 필요한 태블릿, 00이 필요한 노트북이 있다면 두 번째 스위치 하나만 내려도 셋 다 충전된다.

미사키는 집 안 콘센트의 전류를 모두 측정했고, 전부 서로 다르다는 것을 확인했다. 쇼타가 기기를 전부 동시에 충전할 수 있는지 판정하고, 가능하면 내려야 하는 스위치의 최소 개수를 구하라. 스위치가 크고 무거워서 미사키는 필요한 것보다 더 내리고 싶어 하지 않는다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어지고, 각 테스트 케이스는 세 줄로 이루어진다.

첫째 줄에는 정수 $N$과 $L$이 공백으로 구분되어 주어진다. 둘째 줄에는 콘센트가 처음에 내보내는 전류를 나타내는 길이 $L$의 문자열 $N$개가 공백으로 구분되어 주어진다. 셋째 줄에는 쇼타의 기기가 충전에 필요로 하는 전류를 나타내는 길이 $L$의 문자열 $N$개가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 150$
• $2 \le L \le 40$
• 처음에 같은 전류를 내보내는 콘센트는 없다.
• 같은 전류를 필요로 하는 기기는 없다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 쇼타가 모든 기기를 충전하려면 내려야 하는 스위치의 최소 개수다. 모두 충전하는 방법이 없으면 $y$ 자리에 따옴표 없이 NOT POSSIBLE을 출력한다.

첫 번째 예제의 첫째 테스트 케이스에서는 두 번째 스위치를 한 번 내리면 콘센트의 전류가 차례로 00, 10, 11이 된다. 그러면 0번 콘센트로 1번 기기를, 1번 콘센트로 2번 기기를, 2번 콘센트로 0번 기기를 충전한다. 스위치를 하나도 내리지 않으면 충전할 수 없으므로 최소 개수는 1이다.