Labyrinth

The northern part of the Pyramid contains a very large and complicated labyrinth. The labyrinth is divided into square blocks, each of which is either filled with rock or free. In the center of the floor of every free block there is a small hook. Connecting two of these hooks with a rope opens a secret door; the rope must run through the hooks of every block on the path between the two connected blocks. The trouble is that we do not know in advance which two hooks must be connected, so the required length of the rope is unknown as well. Your task is to determine the maximum length of rope we could possibly need for a given labyrinth.

The first line of the input contains the number of test cases T. Each test case begins with a line containing two integers C and R (3 ≤ C, R ≤ 1000), the number of columns and the number of rows. Then exactly R lines follow, each containing C characters. Each character is either a hash mark (#) or a period (.). A hash mark represents a rock and a period represents a free block. You may move only between neighbouring blocks that share a common side; diagonal moves are not allowed and you may not step outside the labyrinth. The labyrinth is designed so that there is exactly one path between any two free blocks.

For each test case print exactly one line. The line must contain the sentence Maximum rope length is X., where X is the length of the longest path between any two free blocks. The length is measured as the number of moves (steps between adjacent blocks) along that path, so a labyrinth with a single free block has length 0.