Гра Місто
Боб є спеціалістом з програмування стратегічних ігор. У його новій грі з будівництва міста ігрове середовище виглядає наступним чином: місто складається з районів, в яких є вулиці, дерева, заводи та будівлі. У районі є ще трохи вільного простору, який не зайнятий. Стратегічне завдання його гри полягає в тому, щоб отримати якомога більше орендної плати з цих вільних просторів. Щоб отримати орендну плату, ви повинні зводити будівлі, які можуть бути лише прямокутними, якомога довшими та ширшими. Боб намагається знайти спосіб побудувати найбільшу можливу будівлю в кожному районі. Але він стикається з деякими проблемами - йому не дозволено знищувати вже існуючі будівлі, дерева, заводи та вулиці в районі, де він будує.
Кожен район має свою ширину та довжину. Район поділений на сітку з рівних квадратних одиниць. Орендна плата за кожну одиницю, на якій стоїть ваша будівля, становить 3$.
Ваше завдання - допомогти Бобу вирішити цю проблему. Все місто поділене на K районів. Кожен з районів є прямокутним і має різний розмір сітки зі своєю довжиною M та шириною N. Існуючі зайняті одиниці позначені символом R. Незайняті одиниці позначені символом F.
Вхідні дані
Перша строка вхідних даних містить ціле число K - що визначає кількість наборів даних. Наступні строки містять описи районів. Один опис визначається наступним чином: Перша строка містить два цілі числа - довжину району M ≤ 1000 та ширину N ≤ 1000, розділені пробілом. Наступні M рядків містять N символів, які позначають зарезервовані або вільні одиниці сітки, розділені пробілом. Використовуються такі символи:
R - зарезервована одиниця
F - вільна одиниця
В кінці кожного опису району є розділювальна строка.
Вихідні дані
Для кожного набору даних у вхідних даних виведіть в окремому рядку, на стандартний вихід, ціле число, яке представляє прибуток, отриманий від зведення найбільшої будівлі в районі, закодованому набором даних.