마법 자물쇠

뉴트는 여러 개의 마법 자물쇠로 잠긴 문을 열어야 한다. 각 자물쇠는 $n_i \times m_i$ 크기의 격자판이며, 각 칸에는 소문자 라틴 알파벳이 하나씩 적혀 있다. 격자판에서 변을 공유하는 인접한 칸들이 이어져 만든 칸의 수열을 사이클이라고 하는데, 마지막 칸과 첫 칸도 인접해야 한다. 같은 칸을 두 번 지나지 않는 사이클은 단순 사이클이다. 두 사이클이 같은 칸을 하나라도 포함하면 서로 교차한다고 한다. 자물쇠를 열려면 같은 글자가 적힌 칸만 지나는, 서로 교차하지 않는 단순 사이클을 최대한 많이 골라야 한다.

뉴트는 사이클을 몇 개 골라야 하는지, 그리고 몇 가지 경우를 확인해야 하는지 모른다. 각 자물쇠마다 고를 수 있는 사이클의 최대 개수와, 그 최대 개수를 고르는 서로 다른 방법의 수를 구하라. 방법의 수가 $10^{18}$을 초과하면 -1을 출력한다. 두 방법은 한쪽에서는 두 칸이 같은 사이클에 속하고 다른 쪽에서는 속하지 않으면 서로 다른 방법이다.

첫 줄에 자물쇠의 개수 $t$가 주어진다 ($1 \le t \le 20$).

각 자물쇠는 격자판의 크기 $n_i$, $m_i$가 주어지는 줄로 시작한다 ($1 \le n_i \cdot m_i \le 160$). 이어지는 $n_i$개의 줄에는 각각 $m_i$개의 소문자 라틴 알파벳이 주어진다.

각 자물쇠마다 한 줄에 두 정수를 출력한다. 첫 번째는 같은 글자가 적힌 칸만 지나고 서로 교차하지 않는 단순 사이클을 $i$번째 격자판에서 고를 수 있는 최대 개수이다. 두 번째는 그 최대 개수를 고르는 방법의 수이다. 방법의 수가 $10^{18}$을 초과하면 두 번째 값 대신 -1을 출력한다.

첫 번째 테스트에서 사이클을 하나 고르는 모든 방법:

두 번째 테스트에서 사이클을 두 개 고르는 유일한 방법: