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