Cho bảng vuông kích thước \(N \times N (2 \le N \le 100)\), mỗi ô có chứa số \(0\) hoặc \(1\). Có một con robot đi từ ô \((1, 1)\) đến ô \((N, N)\) theo hướng từ trên xuống hoặc từ trái qua phải. Trên đường đi, khi đi qua một ô, robot sẽ ghi nhận giá trị của ô đó và tạo thành một số nhị phân tương ứng.

Robot này rất thông minh nên chọn đi qua những ô sao cho tạo thành số nhị phân lớn nhất. Số nhị phân này khá dài, bạn hãy chuyển số nhị phân đó sang giá trị tương ứng trong hệ đếm Hexa.

Dữ liệu vào

• Dòng đầu tiên chứa số \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số (\(0\) hoặc \(1\)). Các số trên cùng một dòng được cách nhau ít nhất một khoảng trắng.

Dữ liệu ra

• Giá trị Hexa tìm được.

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 1

Output 1

177