该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Given an $n \times n$ matrix, an Increasing Path in the matrix is a path which starts at an arbitrary cell, and where the values of cells along the path are strictly increasing. Design an algorithm to find a longest increasing path in a given input matrix, and output the path's length.

Format

Input

An $n\times n$ matrix $M$, which each cell contains a value $M_{i,j}$.

Output

The length of a longest increasing path in the matrix.

Constraints

$1\leq n\leq 200$ $0\leq M_{i,j}\leq 2^{31}-1$ for $A_{i,j}\in A$

Samples

[[3, 4, 5], [3, 2, 6], [2, 2, 7]]

5

[[9, 9, 3], [6, 6, 8], [2, 1, 1]]

4

[[1]]

1