물?

큐리오시티 탐사선을 화성으로 보낸 주요 목표 중 하나는, 화성 표면에 과거에(어쩌면 지금도) 물이 있었을지 모른다는 증거를 더 찾는 것입니다. 물이 있었는지 판단하기 위해 과학자들은 녹(산화)의 흔적처럼 사진 속의 여러 단서를 이용합니다. 이 문제에서는 화성 표면 사진을 살펴보며 물의 증거가 있다면 찾아냅니다.

각 사진은 $h \times w$ 픽셀 크기의 직사각형으로 주어지며, $1 \le h, w \le 50$ 입니다. 각 픽셀은 어떤 물질의 종류를 나타내고, 대문자 알파벳 A부터 Z까지의 한 글자로 표기됩니다(그 밖의 값은 나타나지 않습니다). 이 글자들 중 일부는 특수 글자로 지정되어 있으며, 이는 물을 가리키는 단서입니다. 최소 크기 $m$($1 \le m \le \min(h, w)$)이 주어질 때, 높이와 너비가 모두 $m$ 이상인 모든 축에 평행한 부분 직사각형 가운데 특수 글자의 밀도가 가장 큰 값을 구하세요.

어떤 직사각형의 밀도는 그 안에 들어 있는 특수 픽셀의 개수를 전체 픽셀 수로 나눈 값입니다.

첫 줄에는 데이터 집합의 개수 $K$가 주어집니다. 이어서 $K$개의 데이터 집합이 각각 다음 형식으로 주어집니다.

• 한 줄에 세 정수 $h$, $w$, $m$이 주어집니다. 각각 이미지의 높이, 이미지의 너비, 최소 직사각형 크기입니다.
• 특수 글자를 나타내는 한 줄이 주어집니다. A–Z 중 서로 다른 대문자 $1$개에서 $26$개로 이루어진 문자열이며(정렬되어 있지 않을 수 있습니다), 이 글자들이 물을 가리키는 특수 글자입니다.
• 이어서 $h$개의 줄이 주어지며, 각 줄은 정확히 $w$개의 대문자로만 이루어져 이미지의 한 행을 나타냅니다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력합니다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작합니다. 다음 줄에는 최대 밀도를 분수 a/b 형태로 출력합니다. 이때 $a$는 특수 픽셀의 개수, $b$는 선택한 직사각형의 전체 픽셀 수이고, 높이와 너비가 모두 $m$ 이상인 직사각형만 고려합니다.

분수는 센 값 그대로 출력하며 약분하지 않습니다(예: 1/2가 아니라 8/16). 최대 밀도를 달성하는 직사각형이 여러 개라면 전체 픽셀 수 $b$가 가장 큰 것을 선택합니다. 이렇게 하면 답이 유일하게 정해집니다.

서로 이웃한 데이터 집합 사이에는 빈 줄을 하나 넣어 구분합니다.