The Indigo World Cup, the grandest Pokémon battle, is about to be held in Indigo City. This year, the League Council plans to build the largest Pokémon battle center ever. Ash, now a member of the League Council, wants to identify the largest contiguous patch of clear land in Indigo City to construct the arena. However, Team Rocket is scheming to sabotage the construction and has scattered obstacles throughout the city.
Professor Oak has provided Ash with a grid map of the city. Each tile is marked with a letter:
'C' — clear land, safe to build on.
'R' — rock or obstacle, cannot be built on.
Your task is to help Ash determine the maximum area (number of tiles) of a rectangle that can be constructed using only clear land tiles ('C').
Constraints
1 ≤ t ≤ 10 — number of test cases
1 ≤ number of rows (m) ≤ 200
1 ≤ number of columns (n) ≤ 200
Each cell contains either 'C' (clear) or 'R' (obstacle)
Input Format
First line: an integer t — number of test cases
For each test case:
First line: two integers m n — number of rows and columns
Next m lines: each line contains n characters (no spaces), each either 'C' or 'R'
Output Format
For each test case, output a single integer: the area of the largest rectangle of 'C' cells.
Example 1
Input:
1
4 5
CRCCC
CCCRC
CCCCC
RCCRC
Output:
6
Explanation:
The maximum rectangular area of clear land has 6 tiles. It spans rows 2–3 and columns 1–3 (1-indexed).
Log In to solve the Question