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