Yet Satisfiability Again!#7535
Alice recently started to work for a hardware design company and as a part of her job, she needs to identify defects in fabricated integrated circuits. An approach for identifying these defects boils down to solving a satisfiability instance. She needs your help to write a program to do this task.
The first line contains a single integer, not more than , indicating the number of test cases to follow. The first line of each test case contains two integers (1 \leq n \leq 20) and (1 \leq m \leq 100), where indicates the number of variables and indicates the number of clauses. Then lines follow corresponding to each clause. Each clause is a disjunction of literals in the form 'X[i]' or 'X[i]' for some (1 \leq i \leq n), where 'X[i]' indicates the negation of the literal 'X[i]'. The "or" operator is denoted by a 'v' character and is separated from literals with a single space.
For each test case, display 'satisfiable' on a single line if there is a satisfiable assignment; otherwise display 'unsatisfiable'.
Example 1