Задачи
Компьютерная игра
Компьютерная игра
Джон и Брюс играет военно-стратегическую игру на компьютере. Игра ведется на плоской карте мира. В начале игры Брюс выбирает места для своей армии, а затем Джон должен выбрать стратегические точки для своей армии в соответствии со следующими правилами:
\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}) будут различны.
Входные данные #1
2 2 1 7 7 2 3 0 0 4 -7 7 -4
Выходные данные #1
20 4