Задачі
Комп`ютерна гра
Комп`ютерна гра
Джон та Брюс грають у військово-стратегічну гру на комп`ютері. Гра ведеться на плоскій карті світу. На початку гри Брюс вибирає місця для своєї армії, а потім Джон повинен вибрати стратегічні пункти для своєї армії у відповідності з наступними правилами:
\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