题目描述

小可是学校足球队的队长。球队有一件传奇球衣，上面有历届队长的签名。

这件球衣的传递规则很特殊：

1. 球衣只能在队员之间有偿转让，转让价格是 '0'~'9' 的数字。
2. 队员 $i$ 把球衣卖给队员 $j$ 的价格，必须大于等于 $i$ 当初买下它时支付的价格。
3. 每个人最多拥有这件球衣一次。

一开始，小可（编号 $0$）从退役老队长那里免费得到球衣（价格 $0$）。

现在给定一个 $N \times N$ 的价格表，第 $i$ 行第 $j$ 列的字符 $a_{i,j}$ 表示：队员 $i$ 可以以价格 $a_{i,j}$ 把球衣卖给队员 $j$。（'0' 表示最低价格，'9' 表示最高价格）

请问，最多能有多少名队员拥有过这件球衣（包括小可和最后持有者）？

输入格式

第一行一个整数 $N$，表示队员人数（$2 \le N \le 15$）。

接下来 $N$ 行，每行一个长度为 $N$ 的字符串，只包含 '0'~'9'。

输出格式

输出一个整数，表示答案。

样例

2
01
10

2

3
022
101
110

2