q.py

from __future__ import print_function
from itertools import *

def find_switches(a,b):
    return {i for i,v in enumerate(a) if v != b[i]}

def transform(a,switchs):
    r = ""
    for i, v in enumerate(a):
        if i in switchs:
            v = "0" if v == "1" else "1"
        r += v
    return r

def hashset(x):
    return ''.join(map(str,sorted(x)))

def gen_switchs(curr, goal):
    tested = set()
    alll = []
    for c in curr:
        for g in goal:
            for s in find_switches(c,g),find_switches(g,c):
                h = hashset(s)
                if s and h not in tested:
                    tested.add(h)
                    alll.append(s)
    return sorted(alll, key=lambda x:len(x))

def solve(curr, goal):
    if set(curr) == set(goal):
        return 0
    goal = set(goal)
    N = len(curr[0])
    for switchs in gen_switchs(curr, goal):
        curr2 = set([transform(w, switchs) for w in curr])
        """
        print("sw", switchs)
        print("from",curr, goal)
        print("to",curr2, goal, curr2 == goal)
        """
        if curr2 == goal:
            return len(switchs)
    return "NOT POSSIBLE"

lines = open('in').readlines()
T = int(lines[0])
lines = lines[1:]
for t in range(T):
    curr = lines[1].split()
    goal = lines[2].split()
    s = solve(curr, goal)
    print("Case #%d:" % (t+1), s)
    lines = lines[3:]