28822번 - Волшебные замки 다국어

Ньюту нужно открыть дверь, запертую на несколько волшебных замков. Каждый замок представляет из себя поле $n_i \times m_i$ клеток, в каждой из которых написана одна латинская буква. Циклом на клетчатом поле называется последовательность клеток, в которой каждая пара соседних клеток (в том числе, первая и последняя) имеют общую сторону. Простым циклом называется цикл, который не содержит ни одну клетку дважды. Два цикла пересекаются, если они оба содержат одну и ту же клетку. Чтобы открыть замок, нужно выделить на поле какое-то максимальное возможное количество непересекающихся простых циклов, каждый из которых проходит по клеткам, на которых написана одинаковая буква.

Ньют не знает, сколько циклов он должен выделить, и сколько вариантов ему придется перебрать. Помогите Ньюту: определите максимальное количество таких циклов для каждого замка, а также количество различных способов выделить максимальное количество таких циклов, либо сообщите, что количество способов превышает $10^{18}$. Два способа являются различными, если в одном из них две клетки принадлежат одному циклу, а в другом --- нет.

Первая строка входных данных содержит единственное целое число $t$ --- количество замков ($1 \le t \le 20$).

Далее дано описание $t$ замков. Описание каждого замка начинается со строки, в которой содержится два целых числа $n_i$ и $m_i$ --- размеры $i$-го поля ($1 \le n_i \cdot m_i \le 160$). В следующих $n_i$ строках содержится по $m_i$ строчных латинских букв --- $i$-е поле.

Для каждого замка выведите в отдельной строке два целых числа --- максимальное количество простых непересекающихся циклов, проходящих по клеткам с одинаковой буквой, которые можно выделить на поле $i$-го замка, и количество способов это сделать. Если количество способов строго больше $10^{18}$, выведите вместо этого $-1$.

Все варианты выделения одного цикла в первом тесте:

Единственный способ выделить два цикла во втором тесте: