Given a grid made of '.' and '#', you begin at (0, 0) the top left corner. It is guaranteed that (0, 0) will be a '.' The grid is n × m, with 4 <= n, m <= 100. You can move up/down/left/right/all_diagonals, with a move cost of 1. What is the furthest distance that you can reach from (0, 0) ?

Input

Given T, the number of test cases. Following this are T data sets, with the first line stating N and M. Following this are N strings consisting of '.' and '#', each containing M characters.

Output

T lines containing the maximum distance from the starting location (0, 0) in each test case.

Example

Input:
2
4 4
.#.#
.#..
.##.
....
3 9
.#...#...
.#.#.#.#.
...#...#.

Output:
7
10