미로

피라미드의 북쪽에는 매우 크고 복잡한 미로가 있다. 미로는 정사각형 블록들로 나뉘며, 각 블록은 바위로 막혀 있거나 비어 있다. 비어 있는 모든 블록의 중앙 바닥에는 작은 고리가 하나씩 달려 있다. 두 고리를 밧줄로 연결하면 비밀의 문이 열리는데, 이때 밧줄은 연결한 두 블록 사이 경로에 놓인 모든 블록의 고리를 지나가야 한다. 문제는 어느 두 고리를 연결해야 하는지 미리 알 수 없다는 점이다. 따라서 필요한 밧줄의 길이도 알 수 없다. 주어진 미로에서 우리가 필요로 할 수 있는 밧줄의 최대 길이를 구하여라.

입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 열의 수 C와 행의 수 R (3 ≤ C, R ≤ 1000)이 공백으로 구분되어 주어진다. 이어서 정확히 R개의 줄이 주어지며, 각 줄은 C개의 문자로 이루어진다. 각 문자는 해시(#) 또는 마침표(.) 중 하나다. 해시는 바위를, 마침표는 비어 있는 블록을 나타낸다. 이동은 변을 맞대고 있는 인접한 블록 사이에서만 가능하다. 대각선으로는 이동할 수 없으며, 미로 밖으로 나갈 수도 없다. 미로는 임의의 두 비어 있는 블록 사이에 경로가 정확히 하나만 존재하도록 설계되어 있다.

각 테스트 케이스마다 정확히 한 줄을 출력한다. 그 줄은 Maximum rope length is X. 형태의 문장이어야 하며, 여기서 X는 임의의 두 비어 있는 블록 사이의 가장 긴 경로의 길이다. 길이는 그 경로를 따라 인접한 블록으로 이동하는 횟수(걸음 수)로 센다. 따라서 비어 있는 블록이 하나뿐인 미로에서는 길이가 0이다.