Рабочее место участника

Начинается зима, но в городе К на дорогах все еще продолжается ремонт. После того, как очередная дорога была отремонтирована, департамент транспорта пришел к выводу, что дешевле обслуживать дороги с односторонним движением.

Сейчас все дороги в городе К двусторонние. Дорога состоит из двух полос – встречного и попутного направления. Требуется превратить максимальное количество дорог в односторонние, оставив одну из двух полос так, чтобы сообщение между точками города не нарушилось. Это означает, что если из точки `i` можно проехать в точку `j` (прямо или через промежуточные точки), то после введения одностороннего движения эта возможность должна остаться.

Карта города задаётся матрицей смежности `M`, заполненной нулями и единицами. Размерность матрицы `N` (`1\ ≤\ N\ ≤\ 100`) – число точек города. Если `M[i,\ j]\ =\ 1`, то существует полоса для перемещения из точки `i` в точку `j`, не проходящая через другие точки, иначе `M[i,\ j]\ =\ 0` (`M[i,\ i]\ =\ 0` для любого `i`). Матрица `M` симметрична относительно главной диагонали, т.е. `M[i,\ j]\ =\ M[j,\ i]`, что означает двустороннюю дорогу (полоса встречного и попутного направления).

Во входном файле – несколько тестов. Первая строка входа содержит количество тестов. Для каждого теста на новой строке число `N` – размерность матрицы `M`, следующие `N` строк, каждая по `N` символов (нули или единицы), разделенных пробелами – элементы матрицы `M`.

Для каждого теста в выходной файл выводится результат – максимально возможное число двусторонних дорог, которые можно превратить в односторонние.

2
4
0 0 1 1
0 0 0 0
1 0 0 1
1 0 1 0
7
0 1 0 1 0 0 0
1 0 0 1 0 1 0
0 0 0 0 1 1 1
1 1 0 0 0 0 0
0 0 1 0 0 1 0
0 1 1 0 1 0 0
0 0 1 0 0 0 0

3
6