题目描述

对于一个 $n$ 行 $m$ 列的二维数组，第 $i$ 行、第 $j$ 列上的元素是 $a_{i,j}$。

你可以选择一个数 $a_{i,j}$，然后可以按照这个规则移动：每次可以移动到上下左右四个位置中的 $a_{i,j}$ 的真因数中。

• 如果 y%x==0，那么就称 $x$ 是 $y$ 的因数。
• 如果 $x$ 是 $y$ 的因数，且 $x\neq y$，那么就称 $x$ 是 $y$ 的真因数。

请问怎么选择可以让移动路线尽可能长？

输入格式

输入第一行为两个整数 $n$、$m$。

接下来 $n$ 行，每行有 $m$ 个数，第 $i$ 行、第 $j$ 列上的元素是 $a_{i,j}$。

输出格式

输出最长移动路线的长度。

样例

3 3
1 2 3
5 4 6
9 8 24

5

样例 1 说明

24->8->4->2->1

数据范围

对于 $60\%$ 的数据：$1\le n,m \le 10$；

对于 $100\%$ 的数据：$1\le n,m,a_{i,j} \le 1000$