가장 재미있는 단어 찾기

Siv의 생일이 다음 주인데, Cel이 그녀를 위해 생일 선물을 준비하고 있다. Siv는 퍼즐을 좋아하기 때문에, Cel은 선물로 단어 찾기 퍼즐을 만들고 있다.

단어 찾기 퍼즐에서 풀이자는 R개의 행과 C개의 열로 이루어진 직사각형 격자를 받고, 그 안에 숨겨진 유효한 단어를 모두 찾아야 한다. 숨겨진 각 단어는 가로 또는 세로로(대각선은 안 됨) 정방향이나 역방향으로 나타날 수 있다. 숨겨진 단어끼리는 겹칠 수 있다.

Cel에게는 서로 다른 W개의 단어가 담긴 사전이 있으며, 이 단어들만 퍼즐 격자에 숨길 수 있다. 격자의 가로나 세로 연속 부분마다 숨겨진 단어가 반드시 들어 있는 것은 아니다. 이 단어들이 실제 영어 단어일 필요는 없다. 각 단어는 격자에 한 번 이상 나타나거나 전혀 나타나지 않을 수 있다.

Cel은 이미 퍼즐을 만들었지만, 종이 한 장에 인쇄하기에는 너무 크다. Siv의 생일이 곧 다가와서 새 퍼즐을 처음부터 만들 시간이 없다. 그래서 Cel은 원래 격자의 격자선에 맞춰 비어 있지 않은 부분 격자를 골라 격자 크기를 줄이려고 한다.

무작위로 부분 격자를 고르면 숨겨진 단어가 적어 재미없는 퍼즐이 될 수 있다. 그래서 Cel은 재미 값(fun value)이 가장 큰 부분 격자를 고르고 싶어 한다. 부분 격자의 재미 값은 다음과 같이 정의한다.

$\text{fun value} = \frac{\text{일치한 단어 길이의 합}}{\text{부분 격자의 너비} + \text{부분 격자의 높이}}$

참고:

• 단어 전체가 부분 격자 안에 있어야 개수에 포함된다.
• 단어가 부분 격자에 x번 나타나면, 그 단어의 길이를 위 식에 x번 더한다.
• 단어와 그 역순 단어가 모두 부분 격자에 나타나면(같은 위치에 있더라도) 두 번의 출현을 모두 센다.
• 재미 값이 가장 큰 부분 격자가 원래 격자 전체일 수도 있다.

Cel을 도와 부분 격자가 가질 수 있는 가장 큰 재미 값과, 그 값에 도달하는 서로 다른 부분 격자의 개수를 구하라. 두 부분 격자가 다르다는 것은 어떤 칸(행, 열 위치)이 한쪽에는 속하고 다른 쪽에는 속하지 않는다는 뜻이다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 다음과 같이 주어진다.

• 첫 줄에 위에서 설명한 정수 R, C, W가 주어진다.
• 다음 R줄에는 각각 정확히 C개의 대문자 영어 알파벳이 주어진다.
• 다음 W줄에는 각각 유효한 단어 하나가 주어진다. 단어는 대문자 영어 알파벳으로만 이루어진다.

각 테스트 케이스마다 한 줄에 Case #x: y/z n 형식으로 출력한다.

• x는 테스트 케이스 번호이며 1부터 시작한다.
• y/z는 부분 격자의 가능한 최대 재미 값을 기약분수로 나타낸 것이다. y는 0 이상의 정수이고 z는 양의 정수이다.
• n은 재미 값이 y/z와 같은 부분 격자의 개수이다.

y와 z의 최대공약수는 1이다.

• 1 ≤ T ≤ 100.
• 1 ≤ R ≤ 100.
• 1 ≤ C ≤ 100.
• 유효한 단어 목록에 같은 단어가 두 번 나타나지 않는다.
• 유효한 단어 목록에 있는 모든 단어의 길이 합은 최대 5000글자이다.