Bob是策略游戏程序开发专家。他最新的游戏是一个城市建设游戏。
游戏背景是：
一个城市，是有很多区域组成的，每个区域中有街道、树木、工厂和一些建筑物等，另外还有一些未被占用的空地。游戏的任务就是通过这些空地来赚钱。
要想赚钱，得在这些空地上建造一些建筑物，建筑物必须是矩形的，所以建筑物的面积越大越好。建造中，不能损坏已有的那些街道、树木、工厂等。
每一个区域都有一定的宽和长，可以看成是多个相同的小方格，每个小方格的租金是3$。
假设整个城市一共有K个这样的区域，每个区域也都是矩形的，矩形的长和宽分别是M和N，可以把区域看成是M*N的的网格，如果这个网格中的小方格已经被占就标记为R，如果没有被占就标记为F。
你的任务是帮助Bob找到每个区域中，如何在空地上建造出最大面积的矩形建筑物，并输出租赁这个建筑物所获得的利润。

输入文件的第一行，是一个整数K，表示区域的总个数，也就是测试数据的组数。
对于每组测试数据：
第一行，是用空格隔开的两个整数M和N，表示这个区域的长和宽，即区域是一个M*N的网格（M≤1000，N≤1000）
接下来M行，每行N个字符（字符是F或R），描述M*N个网格中，每个小方块的情况，是被占了还是没有被占。（R表示已经被占，F表示没有被占）

对于每组测试数据，输出租赁这个区域中面积最大的建筑物获取的利润。（即找出区域中全部由F组成的面积最大的子矩阵，输出其面积乘以3后的结果）

计算几何 UVA level6