Джон и Брюс играет военно-стратегическую игру на компьютере. Игра ведется на плоской карте мира. В начале игры Брюс выбирает места для своей армии, а затем Джон должен выбрать стратегические точки для своей армии в соответствии со следующими правилами: \begin{itemize} \item каждой стратегической точкой должны быть точки решетки (\textbf{x}, \textbf{y}) (точкой решетки является точка с целыми координатами) такие, что |\textbf{x}| + |\textbf{y}| < \textbf{N}; \item Джон может выбрать любое число стратегических точках; \item все стратегические пункты должны быть различны; \item каждая из стратегических точек должна быть свободной (т.е. не занятая армией Брюса); \item каждая пара различных стратегических точек должна быть связана (возможно, через какие-либо другие стратегические точки). \end{itemize} Две разных точки решетки (\textbf{x_1, y_1}) и (\textbf{x_2, y_2}) связаны, если |\textbf{x_1 -- x_2}| + |\textbf{y_1 -- y_2}| = \textbf{1}. Если \textbf{A}, \textbf{B} и \textbf{С} являются стратегическими пунктами, и \textbf{А} с \textbf{B} связаны, а \textbf{B} с \textbf{C} связаны, то \textbf{А} с \textbf{С} также связаны. \InputFile Первая строка содержит одно целое \textbf{Т} - количество тестов. Каждый тест начинается со строки, содержащей два целых числа \textbf{N} и \textbf{M}, разделенных одним пробелом. \textbf{N} является количеством, указанном в первом правиле. \textbf{М} - число целых точек на карте мира, уже заняты армией Брюса. Каждая из следующих \textbf{M} строк содержит два целых числа \textbf{Хk} и \textbf{Yk}, разделенных одним пробелом. Каждая точка \textbf{(Xk, Yk)} занята армией Брюса. \OutputFile Для каждого теста распечатать одну строку, содержащую ряд способов для Джона выбрать стратегические точки для своей армии. \textbf{Ограничения} \textbf{1} <= \textbf{T} <= \textbf{74}, \textbf{1} <= \textbf{N} <= \textbf{7}, \textbf{1} <= \textbf{M} <= \textbf{225}, \textbf{-7} <= \textbf{X_k, Y_k} <= \textbf{7}, Все (\textbf{X_k, Y_k}) будут различны.