Một bảng vuông gồm ~N~ hàng và ~N~ cột, mỗi ô chứa một số nguyên không âm. Lúc bắt đầu trò chơi, có một người ở ô ~(1, 1)~ di chuyển đến ô ~(N, N)~ bằng cách: trong mỗi bước người đó di chuyển đi xuống hoặc đến bên phải một ô vuông. Hơn nữa, ông ta không thể vào trong ô chứa số 0. Ta xác định giá tiền một đường đi là tích của tất cả các số chứa trong các ô nằm trong đường đó. Một đường tối ưu nếu tổng chữ số 0 ở cuối của giá tiền trong hệ thập phân là nhỏ nhất.

Yêu cầu: Tính tổng các chữ số 0 ở cuối của giá tiền trong đường đi tối ưu.

Input

• Dòng đầu chứa số ~N~, ~1 \le N \le 1000~.
• Mỗi dòng trong ~N~ dòng sau chứa ~N~ số là hiện diện của bảng. Tất cả các số là số nguyên không âm ~\le 1.000.000~ và giữa các số cách nhau ít nhất một dấu cách. Luôn tồn tại một đường tối ưu cho mỗi test.

Output

• Một số nguyên là tổng các chữ số 0 phía cuối của hiện diện thập phân giá tiền trong đường đi tối ưu.

Sample Input 1

4
1 3 0 0
0 8 2 25
6 5 0 3
0 15 7 4

Sample Output 1

2