Підготовка до Залу Змагань
Перед регіональним конкурсом ACM-ACPC директор майданчика та волонтери були дуже зайняті підготовкою до конкурсу. Одним із їхніх завдань було призначити стіл для кожної команди так, щоб жодні дві команди з одного університету не сиділи поруч. Директор майданчика вирішив не витрачати свій час на це завдання і попросив суддів виконати його. Судді подумали, що це може бути хорошою задачею для використання в наборі задач конкурсу. Оскільки вони були дуже зайняті підготовкою до конкурсу, судді вирішили вирішити частину задачі і попросити учасників вирішити решту.
Судді згенерують кілька варіантів розміщення команд за столами і попросять учасників написати програму, яка перевірить, чи є кожне з цих розміщень дійсним чи ні. Якщо розміщення не є дійсним, програма повинна підрахувати, скільки різних університетів мають принаймні дві свої команди, що сидять поруч одна з одною. "Ну, ви можете використати ці рішення для конкурсу наступного року", - сказав головний суддя Ахмед Алі директору майданчика.
Зал для конкурсу можна представити у вигляді 2D сітки з N рядками, кожен з яких містить M клітинок. Кожна клітинка в сітці або зайнята командою, або порожня. Може бути до 8 команд, що знаходяться поруч з однією командою. Команда може мати менше ніж 8 сусідніх команд, якщо вона розташована біля краю залу або деякі з її сусідніх клітинок порожні.
Наприклад, у розміщенні, показаному на наступному рисунку, команда E має 7 сусідніх команд, названих A, B, C, D, F, G та H, тоді як сусідні команди до команди A - це B, D та E.
Вхідні дані
Ваша програма буде протестована на одному або більше тестових випадках. Перша строка введення містить одне ціле число T, кількість тестових випадків (1 ≤ T ≤ 100). Далі йдуть тестові випадки, кожен з яких починається з рядка, що містить 2 цілі числа, розділені одним пробілом N та M (1 ≤ N, M ≤ 100), що представляють розміри залу, після чого йдуть N рядків, кожен з яких містить M цілих чисел, розділених одним пробілом, що представляють розподіл столів у цьому рядку. Кожне ціле число представляє ID університету команди, призначеної до цього столу, або -1, якщо він порожній. Всі ID університетів є додатними цілими числами, не більшими за 100.
Вихідні дані
Для кожного тестового випадку виведіть в одному рядку одне ціле число, кількість різних університетів, що мають принаймні дві свої команди, розташовані поруч одна з одною.