Шаблон блокування
Одним із способів блокування деяких телефонів є використання шаблону блокування. Щоб розблокувати телефон, потрібно намалювати секретний шаблон на сітці з певними точками, де шаблон складається з відрізків, що з'єднують ці точки.
Сітка шаблону вашого телефону складається з чотирьох рядків, у кожному з яких три точки. На наступному зображенні зліва показано представлення сітки, яке можна змоделювати як 2D площину з координатами X та Y для кожної точки. Наприклад, верхня ліва точка має координати (1,4), а нижня права - (3,1). Зображення праворуч демонструє дійсний шаблон, який з'єднує точки в такому порядку: (3,4) (2,4) (1,2) (2,1) (2,2) (3,2) (3,1) (1,3).
Дійсний шаблон має такі властивості:
Шаблон може бути представлений послідовністю точок, яких він торкається вперше (в тому ж порядку, в якому малюється шаблон). Шаблон, що йде від (1,1) до (2,2), не є тим самим, що йде від (2,2) до (1,1).
Для кожної пари послідовних точок A і B у представленні шаблону, якщо відрізок, що з'єднує A і B, проходить через інші точки, ці точки також повинні бути в послідовності і йти перед A і B, інакше шаблон буде недійсним. Наприклад, представлення шаблону, яке починається з (3,1), а потім (1,3), є недійсним, оскільки відрізок проходить через (2,2), яка не з'явилася в представленні шаблону перед (3,1), і правильне представлення для цього шаблону - це (3,1) (2,2) (1,3). Але шаблон (2,2) (3,2) (3,1) (1,3) є дійсним, оскільки (2,2) з'явилася перед (3,1).
У представленні шаблону ми не згадуємо ту саму точку більше одного разу, навіть якщо шаблон знову торкнеться цієї точки через інший дійсний відрізок, і кожен відрізок у шаблоні повинен йти від точки до іншої точки, яку шаблон ще не торкався, і він може проходити через деякі точки, які вже з'явилися в шаблоні.
Довжина шаблону - це сума мангеттенських відстаней між кожною парою послідовних точок у представленні шаблону. Мангеттенська відстань між двома точками (X_1,Y_1) і (X_2,Y_2) - це |X_1-X_2|+|Y_1-Y_2| (де |X| означає абсолютне значення X). Довжина шаблону на зображенні вище: 1 + 3 + 2 + 1 + 1 + 1 + 4 = 13.
Шаблон повинен торкатися принаймні двох точок.
На жаль, ви забули шаблон вашого телефону, але пам'ятаєте довжину шаблону та набір точок S, які точно не торкаються шаблону (точки, які не входять до S, можуть і можуть не торкатися шаблону), і ви вирішили спробувати всі дійсні шаблони, які відповідають тому, що ви пам'ятаєте. Перед тим, як це зробити, ви повинні написати програму, щоб підрахувати для вас кількість різних дійсних шаблонів.
Вхідні дані
Ваша програма буде протестована на одному або більше тестових випадках. Перша строка введення буде містити одне ціле число T, кількість тестових випадків (1 ≤ T ≤ 100). Далі йдуть тестові випадки, перша строка тестового випадку містить два цілі числа L і N, розділені одним пробілом. L (1 ≤ L ≤ 1000) - це довжина шаблону (як описано вище), а N (0 ≤ N ≤ 12) - це кількість точок, які ви впевнені, що вони не торкаються шаблону, далі йдуть N рядків, кожен з яких містить два цілі числа X (1 ≤ X ≤ 3) і Y (1 ≤ Y ≤ 4), розділені одним пробілом, що представляють координати однієї з точок, які точно не торкаються шаблону, N точки є різними.
Вихідні дані
Для кожного тестового випадку, якщо немає дійсних шаблонів відповідно до того, що ви пам'ятаєте, виведіть на одній строке "BAD MEMORY" (без лапок), інакше виведіть кількість різних дійсних шаблонів.