Problem N
北欧のキャンプ

北欧の高地でキャンプをする場合、信頼できる水源があるかどうかは死活問題になります。 伝統的に北欧のキャンパーは、水源地の上にテントを張り、外に出なくてもいつでも水を汲めるようにしてきました。 北欧の人々のもう一つの奇妙な伝統は、テントです。 彼らは正方形のテントしか使いません。

北欧の高地のキャンプ場はとても荒れていたり、岩が多かったりします。 ジョンは現在新しいキャンプ場を設営中で、キャンプ場で使用可能なスポットをすべて調査しています。 キャンプ場を $N$×$M$ のグリッドとして表すと、ジョンは、荒れていて使えないセルのリストを与えてくれます。 ジョンは、与えられた水源をカバーするように、滑らかで使用可能なセルのみを使用して、 自分のキャンプ場に張れる最大のテントの大きさを知りたいと考えています。

それぞれの水源について、ジョンがその水源を覆うように張れる 最大の正方形のテントのサイズを決めるのを手伝ってもらえますか？

図 1: 第2の例のテストケースと、$(3,2)$の水源を覆う最大の正方形のテントです。これは、$(5,4)$の水源を覆う最大の正方形のテントにもなります。

入力

入力の最初の行は、2つの整数$N$と$M$ ($1\leq N,M$)です。 続く$N$行は、それぞれ$M$文字の文字列で、キャンプ場の地図を表します。 地図上の文字は、.（使えるセル）か#（使えないセル）かのいずれかです。

次の行は1つの整数$Q$です。これは、ジョンが検討している水源の数を表します。 続く$Q$行は、2つの整数$r$と$c$ ($1\leq r\leq N$, $1\leq c\leq M$)です。これは、水源の座標$(r,c)$を表します。

出力

ジョンが検討している各水源について、入力と同じ順番で、その特定の水源をカバーするように、滑らかで使用可能なセルに張ることができる最大の正方形テントの面積を出力してください。

テントがセルの一部だけを覆うように張ってはいけないことに注意してください。 セルを完全に覆うか、セルに全くかかっていないかのいずれかである必要があります。

評定

あなたの解答はサブタスクのセットで評価されます。サブタスクは複数のテストケースで構成されます。サブタスクのポイントを得るためには、サブタスクに含まれるすべてのテストケースに合格しなければなりません。

3 3
#..
...
.##
2
1 3
2 1

4
1

5 5
#...#
..#..
.....
#...#
#....
5
3 2
2 5
5 4
4 5
1 3

9
4
9
0
1