Cho lưới ô vuông kích thước ~N \times N~, mỗi ô được tô màu đen hoặc trắng. Tìm trong lưới hình thoi màu trắng trên nền đen lớn nhất (hình thoi có màu trắng và các ô vuông bao xung quanh phải có màu đen). Kích thước của hình thoi là độ dài đường chéo, ta không xét hình thoi chỉ có 1 ô nên kích thước tối thiểu của một hình thoi là ~3~. Hình thoi dưới đây có kích thước 7:

Input

Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 2000)~.

Trong ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ ký tự viết liền nhau. Mỗi ký tự là màu sắc của một ô: * là màu trắng và . là màu đen.

Output

Kích thước hình thoi trắng lớn nhất trên nền đen, nếu không có in ~-1~.

Example

Input

9
..*..*...
.***.**.*
******...
.***.....
*.*...*..
.....***.
.*..*****
***..***.
.*....*..

Output

5