題目說明

系上苦盼的系館，終於有著落了!在地的土地公終於答應讓我們將系館建起，但他有一個要求: 系館必須是正方形的。聰明的我們想到，土地只有要求要正方形，卻沒有規定大小，所以我們希望利用校地所剩餘的空間，將我們的系館最大化。只是這問題比我們想像還複雜，沒辦法用手算。做人一定要靠自己，我們可以透過程式來達到我們的目的嗎?

輸入格式

第一行為幾筆測資~M~(~M \leq 10~)。 接下來每組測資由一個數字~N~代表地圖大小(給定的地圖為~N*N~)。 之後會有~N~行代表地形: -代表空地，X代表地上障礙物，不可在上面建設任何東西。

輸出格式

對於每一筆測資，輸出可興建的最大方形面積。

範例輸入

2
5
X--X-
-----
-----
-----
---X-
8
--X----X
-----X--
X--X----
--X-----
X--X----
XXXX----
--X-----
--X---X-

範例輸出

9
16

評分標準

• 可處理 ~N \leq 10~ 之地形資料。(20分)
• 可處理 ~N \leq 100~ 之地形資料。(20分)
• 可處裡 ~N \leq 1000~ 之地形資料。(60分)