题目描述

在 n*n 的数字矩阵中，从左下角开始，每次只能向上或向右进入相邻的方格，不能走到方格外，一直走到右上角，问路径上数的乘积中 2 的因子最多是多少？

输入格式

第 1 行一个数n，范围 [1,100]；

第 2 到 n+1 行，每行 n 个整数，范围[1,1000]；

输出格式

一个整数。

样例

5
1 2 3 4 5
4 5 6 8 9
5 3 8 12 20
1 10 2 5 3
4 1 27 3 7

14

样例解释

2因子最多的路径序列是 4 1 10 2 8 12 8 4 5