Городская игра
Боб — специалист по программированию стратегических игр. В его новой игре по строительству города игровая среда устроена следующим образом: город состоит из районов, в которых расположены улицы, деревья, заводы и здания. В каждом районе остаётся некоторое свободное пространство. Стратегическая задача игры заключается в том, чтобы извлечь максимальную арендную плату с этих свободных участков. Для этого необходимо строить здания, которые могут быть только прямоугольными и максимально большими. Боб ищет способ построить самое большое возможное здание в каждом районе. Однако он сталкивается с ограничением: нельзя разрушать уже существующие здания, деревья, заводы и улицы в районе, где он строит.
Каждый район имеет свою ширину и длину и разделён на сетку из равных квадратных единиц. Арендная плата за каждую единицу, на которой стоит ваше здание, составляет 3$.
Ваша задача — помочь Бобу решить эту проблему. Весь город разделён на K районов. Каждый из районов является прямоугольным и имеет свою длину M и ширину N. Занятые единицы обозначены символом R, а свободные — символом F.
Входные данные
Первая строка входных данных содержит целое число K — количество наборов данных. Далее следуют описания районов. Одно описание состоит из: первой строки с двумя целыми числами — длиной района M ≤ 1000 и шириной N ≤ 1000, разделёнными пробелом. Следующие M строк содержат N символов, обозначающих зарезервированные или свободные единицы сетки, разделённые пробелом. Используемые символы:
R — зарезервированная единица
F — свободная единица
После каждого описания района следует разделительная строка.
Выходные данные
Для каждого набора данных на входе выведите в отдельной строке на стандартный вывод целое число, представляющее прибыль от возведения самого большого здания в районе, описанном в наборе данных.