Танд сөрөг биш бүхэл тооноос тогтох $n × n$ хүснэгт өгөгдсөн. Та уг хүснэгтээс дараах нөхцлийг хангах замыг олоорой

• Хүснэгтийн зүүн дээд булангаас эхлэх
• Дараагийн нүд нь одоо байгаа нүдний баруун эсвэл доод талынх байх
• Зам баруун доод буланд дуусах

Мөн бид сонгосон замаар явж дууссаны дараа дайрсан нүднүүд дахь тооны үржвэр "хамгийн бага тойрогтой" байх ёстой. Энэ нь уг үржвэр хамгийн цөөн $0$ -р төгсөх ёстой гэсэн үг юм.

Оролт

Эхний мөр хүснэгтний хэмжээ болох $n$ бүхэл тоо байна ($2 ≤ n ≤ 1000$). Дараагийн $n$ мөрөнд хүснэгтийн элементүүд ($10^9$-с хэтрэхгүй эерэг бүхэл тоо) өгөгдөнө.

Гаралт

Эхний мөрөнд хамгийн цөөн байх үржвэрийн төгсгөл дахь $0$-н тоог гарга.

Дараагийн мөрөнд явах замыг хэвлэнэ.