Програмчлалын олимпиадын бодлогын архив

Төөрдөг байшингийн эзэн байшингийнхаа ханын цаасыг солихоор шийджээ. Ингэхийн тулд байшингийн дотор ханын нийт талбайг мэдэх хэрэгтэй болсон. Байшинг NxN хүснэгтээр илэрхийлнэ(3<=N<=33). Хүснэгтийн зарим нүдэнд цэг (‘.’ - тэмдэгт) байх ба энэ нь хоосон квадрат талбайг илэрхийлнэ. Бусад нүдэнд чагт (‘#’ - тэмдэгт) байх ба энэ нь квадрат суурьтай нэг чулуун баганыг илэрхийлнэ. Баганын суурийн талын урт 3м, өндөр нь бас 3м. Байшингийн гадуур битүү (хаалганы үүрэг гүйцэтгэж байгаа зүүн дээд болон баруун доод булангаас бусад газраар) чулуун баганатай ба мөн чагтаар тэмдэглэгдсэн газруудад чулуун багана байгаа.

Төөрдөг байшингийн зочдод харагдаж болох бүх дотоод хананы талбайг ол. Баганууд ерөнхий талтай бол тэдгээрийг хөрш гэнэ. Хөрш хоёр баганы завсраар харах болон шурган орох боломжгүй. Харин ерөнхий нэг булантай хоёр баганы завсраар шурган гарч болно. Дээрх зурагт харагдах ханыг тод зураасаар зурав.

Input

Оролт нь олон тестнээс тогтоно. Эхний мөрөнд тестийн тоо Т байрлана.
Дараагийн мөрүүдэд Т ширхэг тест байна (1<=T<=5).
Тест бүр дараах бүтэцтэй: Тестийн эхний мөрөнд N бүхэл тоо байрлана. Дараагийн N мөр тус бүрд N ширхэг тэмдэгт байна. Мөр бүр төөрдөг байшингийн хүснэгтийн нэг мөрийг илэрхийлнэ. Мөр бүр нь зөвхөн цэг болон чагт тэмдэгтээс тогтох ба мөрийн эцэст мөр шилжүүлэх тэмдэгт байрлана. Оролтонд хоосон зай байхгүй. Оролт нь хүснэгтийн зүүн дээд болон баруун доод буланд цэг үргэлж байхаар өгөгдөнө.

Output

Харагдах хананы нийт талбайг илэрхийлэх ганц бүхэл тоог хэвлэнэ.

Example

Input:
2
5
.....
...##
..#..
..###
.....
2
.#
..

Тайлбар: N=2 гэсэн тест зөвхөн жишээ оролтон дээр байгаа.

Output:
252
36