Условие

---

ГРУПА B, ЗАДАЧА D. ЗАКЛРЪГЛЕН ПЪТ
---
Гошо се загубил в една квадратна матрица с размери n x n, състояща се от неотрицателни цели числа.  Пред Гошо се появил Магьосник, който му казал, че ще успее да избяга от квадратната матрица само ако успее да намери такъв път, че произведението от елементите, през които е минал е число, което е възможно най-малко "кръгло", с други думи има възможно най-малко нули в края си.

Гошо започва движението си в матрицата от горния ляв ъгъл. На всяка стъпка има право да отиде само надолу или надясно. Неговия път винаги трябва да приключва в долния десен ъгъл.

Вход
На първи ред се въвежда цяло число n (2 ≤ n ≤ 1000). Следващите n реда съдържат елементите на матрицата, разделени с по един интервал, като всеки от тях е цяло положително число число, не по-голямо от 10^9.

Изход
На първия ред изведете броя на нулите, на които завършва числото, което се получава с възможно най-малко нули накрая.

Примерен вход 1
4
1 1 9 9
3 4 7 3
7 9 1 7
1 7 1 5

Примерен изход 1
0

Примерен вход 2
3
4 10 5
10 9 4
6 5 3

Примерен изход 2
1

Пояснение: В първи пример съществува път, в който произведението няма нито една нула в записа си. Такъв път може да се постигне с последователност: надолу, надолу, надолу, надясно, надясно, надясно. Числото, което се получава е: 1 * 3 * 7 * 1 * 7 * 1 * 5 = 735