Шаблон блокировки
Один из способов блокировки некоторых телефонов — это графический ключ. Чтобы разблокировать телефон, нужно нарисовать секретный узор на сетке из нескольких точек, узор будет состоять из отрезков, соединяющих эти точки.
Сетка графического ключа вашего телефона состоит из четырех рядов, в каждом из которых по три точки. Следующее изображение слева представляет сетку, которую можно моделировать как 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" (без кавычек), в противном случае выведите количество различных допустимых узоров.