ami có một bảng \(A\) kích thước \(n \times n\). Các hàng và các cột được đánh số từ 1 đến \(n\), ô nằm trên giao của hàng \(i\) và cột \(j\) là ô \(A_{i,j}\).

Hiện tại, ô \(A_{i,j}\) đang được tô màu đen hoặc hồng. Các bạn có thể chọn một hình chữ nhật con bất kỳ trong bảng và biến tất cả các ô thành màu hồng. Nếu hình chữ nhật các bạn chọn có kích thước \(d \times c\) thì các bạn sẽ tốn \(\max(d, c)\) thời gian để thực hiện thao tác. Cần biến tất cả các ô trong bảng thành màu hồng với tổng thời gian là ít nhất.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(n\) là kích thước bảng.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) kí tự \(A_{i,j}\). \(A_{i,j}\) = # biểu thị một ô đen và \(A_{i,j}\) = . biểu thị một ô hồng.

Output

• Một số nguyên là tổng thời gian nhỏ nhất.

Example

1
.

0

3
###
###
###

3

Giới hạn

• \(100\%\) test có \(1 \leq n \leq 50\).