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