#2436 링크 게임

11  1 s   128 MB  

Description

 

격자판 모양의 보드에 R * C 개의 조약돌이 놓여 있습니다. 일반적인 조약돌에는 아무것도 적혀 있지 않지만, 몇 개의 조약돌에는 알파벳이 적혀 있습니다.
알파벳이 적혀 있는 조약돌은 항상 두 개씩 쌍으로 존재합니다.
링크게임은 아래의 조건들을 만족하도록 K 개의 링크를 만드는 게임입니다. 여기서 링크란 여러개의 조약돌을 직선으로 연결한 것을 말하며, K 는 알파벳이 적힌 조약돌 쌍의 수입니다.
 
 1. 각 링크의 시작과 끝은 같은 알파벳이 적혀 있는 조약돌이어야 한다. (즉, 알파벳이 적혀 있지 않은 조약돌이 경로의 시작과 끝에 존재할 수 없다) 
 2. 조약돌은 상하좌우로 인접한 조약돌과 연결할 수 있다. 대각선으로는 연결할 수 없다.
 3. 하나의 조약돌은 반드시 하나의 링크에 포함되어야 한다.
 4. 하나의 링크에서 같은 조약돌을 두 번 이상 지날 수 없다.
 
(6a)과 같이 조약돌이 배치되어 있을 때, (6b) 또는 (6c)의 예와 같이 여러가지 방법으로 격자판의 모든 조약돌을 위의 조건에 맞춰 링크를 만들 수 있습니다.
조약돌의 배치가 입력으로 주어졌을 때, 위의 조건을 만족하는 가능한 경우의 수를 출력하는 프로그램을 작성하세요.

Input

입력은 여러 개의 테스트 케이스로 주어지며, 입력의 첫 줄에는 테스트 케이스 T (1 ≤ T ≤ 100)가 주어집니다. 
각 테스트 케이스마다 첫 줄에 보드의 크기를 나타내는 행의 수 R과 열의 수 C, 그리고 알파벳의 종류 K 가 주어집니다.
R은 1 이상 5 이하의 자연수이고, C 는 1 이상 6 이하의 자연수입니다. 그리고 K 는 1 이상 5 이하의 자연수입니다.
다음 R 줄에 걸쳐 길이 C인 문자열이 주어집니다. 
“*” 표시는 일반 조약돌을 의미하며, 알파벳은 대문자만 입력됩니다. 각 알파벳은 하나의 테스트 케이스에 2개 혹은 0개만 존재합니다.

Output

각 테스트 케이스 별로 조건을 만족하는 가능한 경우의 수를 출력하세요.

Sample Input

Sample Output

3
2 3 2
A*A
B*B
2 2 2
XZ
ZX
3 4 1
T**T
****
****
1
0
4

Source

shake! 2015 본선