Trong 1 lần dạo chơi ở Las Noches , Ulquiora bắt gặp Grimmjow Jaegerjaquez đang thách đố Yammy Llargo bằng 1 bài toán. Vì Yammy rất ngốc nên cậu ta nhờ giúp Ulquiora giải bài toán này và hứa cho cậu ta 1 đàn em Hollow. Trong vài phút Ulquiora đã giải ra, bây giờ Ulquiora thách đố lại các bạn D18 PROPTIT.

Cho một ma trận ~n \times n~ dưới dạng các chỉ số ~0~ và ~1~. Nhiệm vụ của bạn đó chính là tìm đường đi từ điểm bắt đầu đến điểm kết thúc chỉ bằng cách sang phải và đi xuống sao cho số ~S~ tạo bởi đường đi <BIN>, được biểu diễn dưới dạng bát phân <OCT>  nhỏ nhất.

• Điểm bắt đầu: Góc trái trên cùng của ma trận.
• Điểm kết thúc: Góc phải dưới cùng của ma trận.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ ~(1 \leq n \leq 1000)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số (~0~ hoặc ~1~).

Output

In ra số ~S~ ở dạng bát phân <OCT> trên một dòng duy nhất.

Sample

Input #1

5
1 0 1 1 0
0 0 1 0 1
0 0 1 0 1
1 0 0 1 1
1 1 0 1 0

Output #1

402

Problem source: CLB Lập Trình PTIT