Maximum borders
Basic programming
Input/output
65.0% success
69,096 attempts
1s time
256MB memory
1024KB max code

You are given a table with \(n\) rows and \(m\) columns. Each cell is colored with white or black. Considering the shapes created by black cells, what is the maximum border of these shapes? Border of a shape means the maximum number of consecutive black cells in any row or column without any white cell in between.

A shape is a set of connected cells. Two cells are connected if they share an edge. Note that no shape has a hole in it.

Input format

  • The first line contains \(t\) denoting the number of test cases.
  • The first line of each test case contains integers \(n,\ m\) denoting the number of rows and columns of the matrix. Here, '#' represents a black cell and '.' represents a white cell.
  • Each of the next \(n\) lines contains \(m\) integers.

Output format

Print the maximum border of the shapes.

Examples
Input
10
2 15
.....####......
.....#.........
7 9
...###...
...###...
..#......
.####....
..#......
...#####.
.........
18 11
.#########.
########...
.........#.
####.......
.....#####.
.....##....
....#####..
.....####..
..###......
......#....
....#####..
...####....
##.........
#####......
....#####..
....##.....
.#######...
.#.........
1 15
.....######....
5 11
..#####....
.#######...
......#....
....#####..
...#####...
8 13
.....######..
......##.....
########.....
...#.........
.............
#######......
..######.....
####.........
7 5
.....
..##.
###..
..##.
.....
..#..
.#...
14 2
..
#.
..
#.
..
#.
..
..
#.
..
..
..
#.
..
7 15
.###########...
##############.
...####........
...##########..
.......#.......
.....#########.
.#######.......
12 6
#####.
###...
#.....
##....
###...
......
.##...
..##..
...#..
..#...
#####.
####..
Output
4
5
9
6
7
8
3
1
14
5
Explanation

-

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...