Комп`ютерна гра
Джон та Брюс грають у військово-стратегічну гру на комп'ютері. Гра ведеться на плоскій карті світу. На початку гри Брюс вибирає місця для своєї армії, а потім Джон повинен вибрати стратегічні пункти для своєї армії у відповідності з наступними правилами:
кожним стратегічним пунктом повинні бути точки решітки (x, y) (точкою решітки є точка з цілими координатами) такі, що |x| + |y| < N;
Джон може вибрати довільну кількість стратегічних пунктів;
всі стратегічні пункти повинні бути різні;
кажден з стратегічних пунктів повинен бути вільним (тобто не зайнятим армією Брюса);
кожна пара різних стратегічних точок повинна бути зв'язана (можливо, через якісь інші стратегічні точки).
Дві разі точки решітки (x_1, y_1) та (x_2, y_2) зв'язані, якщо |x_1 – x_2| + |y_1 – y_2| = 1. Якщо A, B та С є стратегічними пунктами, і А з B зв'язані, та B з C зв'язані, то А з С також зв'язані.
Вхідні дані
Первший рядок містить одне ціле Т - кількість тестів. Кожен тест починається з рядка, що містить два цілих числа N та M, відокремлених одним пропуском. N є числом, вказаним у першому правилі. М - число цілих точок на карті світу, вже зайнятих армією Брюса. Кожен з наступних M рядків містить два цілих чила Хk та Yk, відокремлених одним пропуском. Кожна точка (Xk, Yk) зайнята армією Брюса.
Вихідні дані
Для кожного тесту вивести один рядок, який містить кількість способів для Джона вибрати стратегічні точки для своєї армії.
Обмеження
1 <= T <= 74,
1 <= N <= 7,
1 <= M <= 225,
-7 <= X_k, Y_k <= 7,
Всі (X_k, Y_k) будуть різні.