크리스마스 트리

N개의 행과 M개의 열로 이루어진 직사각형 격자가 주어진다. 이 격자의 각 칸은 초록색과 흰색 중 하나로 칠해져 있다. 이 격자에서 가장 큰 크리스마스 트리에 포함된 초록색 칸의 수를 구해야 한다.

크리스마스 트리를 정의하기 위해 먼저 좋은 삼각형을 다음과 같이 정의한다.

꼭짓점이 R행 C열에 있고 높이가 h인 좋은 삼각형은 전체가 초록색 칸으로 이루어지고 위쪽을 향하는 이등변삼각형이다. 형식적으로 이는 다음을 의미한다. (R, C) 칸은 초록색이며, 0부터 h-1까지의 각 i에 대해 R+i행에서 C-i열부터 C+i열까지의 모든 칸이 초록색이다.

예를 들면 다음과 같다.

` ..#.. .####

`은 높이가 3인 좋은 삼각형이다. # 칸은 초록색이고 . 칸은 흰색이다. 좋은 삼각형에 닿아 있지만 좋은 삼각형의 일부가 아닌 초록색 칸이 있다는 점에 유의한다.

..#.. .###. ####. 은 3rd 행의 5th 칸이 흰색이므로 좋은 삼각형이 NOT. 하지만 높이가 2인 좋은 삼각형들은 존재한다.

...#. .###. #####. 은 좋은 삼각형이 NOT. 하지만 높이가 2인 좋은 삼각형들은 존재한다.

K-크리스마스 트리는 다음과 같이 정의한다.

• 세로로 배치된 정확히 K개의 좋은 삼각형을 포함한다.

• i+1번째 삼각형의 꼭짓점 칸은 i번째 삼각형 밑변에 있는 칸 중 어느 하나의 아래쪽 모서리와 자신의 위쪽 모서리를 공유해야 한다. 즉, i번째 삼각형의 밑변이 r행의 c1열부터 c2열까지라면, i+1번째 삼각형의 꼭짓점은 r+1행에서 c1열부터 c2열까지 중 어느 한 열에 있어야 한다.

예를 들어 K = 2인 경우:

...#... ..###.. .#####. ####### ..#.... .###... #####.. 은 유효한 2-크리스마스 트리이다. 2개의 좋은 삼각형은 높이가 서로 달라도 된다는 점에 유의한다.

..#.. .###. .#... 도 유효한 2-크리스마스 트리이다. 좋은 삼각형의 높이는 1일 수 있으며 초록색 칸을 하나만 가질 수 있다는 점에 유의한다.

...#... ..###.. .#####. ....... ..#.... .###... #####.. 은 2nd 삼각형이 4번째 행에서 시작해야 하므로 유효한 크리스마스 트리가 NOT.

...#. ..### .#... ###.. 은 2nd 삼각형의 꼭짓점이 3열부터 5열까지 중 한 열에 있어야 하므로 유효한 크리스마스 트리가 NOT.

초록색 칸의 수가 가장 많은 K-크리스마스 트리를 찾아야 한다.

제한

1 ≤ T ≤ 100. 메모리 제한: 1GB. 1 ≤ M ≤ 100. 1 ≤ N ≤ 100. 격자의 각 칸은 . 또는 #이다.

소규모 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. K = 1.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 80초. 1 ≤ K ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 부분으로 이루어진다.

• 첫 줄에는 공백으로 구분된 정수 3 N, M, K가 주어진다. 여기서 N은 격자의 행 수, M은 격자의 열 수, K는 원하는 크리스마스 트리에 포함되는 좋은 삼각형의 수이다.

• 다음 N개의 줄에는 각각 정확히 M개의 문자가 주어진다. 각 문자는 . 또는 #이며, 각각 흰색 칸 또는 초록색 칸을 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 가장 큰 K-크리스마스 트리에 포함된 초록색 칸의 수이다. K-크리스마스 트리가 없다면 0를 출력한다.

예제 케이스 #1에서 가장 큰 1-크리스마스 트리에는 초록색 칸이 9개 있다.

` ..#.. .###.

`

예제 케이스 #2에는 1-크리스마스 트리가 없다.

예제 케이스 #3에서 초록색 칸이 9개인 가장 큰 1-크리스마스 트리 중 하나는 다음과 같다.

` #####

`

예제 케이스 #4에서 초록색 칸이 10개인 가장 큰 2-크리스마스 트리 중 하나는 다음과 같다.

` #####

`