Виконуваність знову!
Аліса нещодавно почала працювати над апаратною розробкою в компанії, і її завдання полягає у виявленні дефектів у готових інтегральних схемах. Виявлення цих дефектів зводиться до розв'язання задачі виконуваності. Допоможіть Алісі написати програму, яка розв'язує цю задачу.
Вхідні дані
Перший рядок містить кількість тестів, не більше 5. Перший рядок кожного тесту містить два числа n (1 ≤ n ≤ 20) і m (1 ≤ m ≤ 100), де n - кількість змінних, а m - кількість правил. Кожен з наступних m рядків задає одне правило. Кожне правило представляє собою диз'юнкцію літералів виду X[i] або ~X[i] для деякого i (1 ≤ i ≤ n), де ~X[i] позначає заперечення літерала X[i]. Оператор "or" позначається символом v і відділяється від літералів одним пробілом.
Вихідні дані
Для кожного тесту вивести в окремому рядку satisfiable, якщо формула виконується, і unsatisfiable інакше.