Codeforces Round 952 (Div. 4) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

data structures

dfs and similar

dsu

graphs

implementation

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
H1. Maximize the Largest Component (Easy Version)

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputEasy and hard versions are actually different problems, so read statements of both problems completely and carefully. The only difference between the two versions is the operation.

Alex has a grid with $$$n$$$ rows and $$$m$$$ columns consisting of '.' and '#' characters. A set of '#' cells forms a connected component if from any cell in this set, it is possible to reach any other cell in this set by only moving to another cell in the set that shares a common side. The size of a connected component is the number of cells in the set.

In one operation, Alex selects any row $$$r$$$ ($$$1 \le r \le n$$$) or any column $$$c$$$ ($$$1 \le c \le m$$$), then sets every cell in row $$$r$$$ or column $$$c$$$ to be '#'. Help Alex find the maximum possible size of the largest connected component of '#' cells that he can achieve after performing the operation at most once.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$) — the number of rows and columns of the grid.

The next $$$n$$$ lines each contain $$$m$$$ characters. Each character is either '.' or '#'.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the maximum possible size of a connected component of '#' cells that Alex can achieve.

Example

Input

61 1.4 2..#.#..#3 5.#.#...#...#.#.5 5#...#....##...#........##6 6.#..#.#..#...#...##.#.#..#.##.###..#6 8..#....#.####.#.###.#..#.##.#.##.#.##.###..##.#.

Output

1 6 9 11 15 30

Note

In the second test case, it is optimal for Alex to set all cells in column $$$2$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$6$$$.

In the third test case, it is optimal for Alex to set all cells in row $$$2$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$9$$$.

In the fourth test case, it is optimal for Alex to set all cells in row $$$4$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$11$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/24/2024 04:01:29 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|