#T1176. 下落

下落

题目描述

对于一个 nnmm 列的二维数组,第 ii 行、第 jj 列上的元素是 ai,ja_{i,j}

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

  • 如果 y%x==0,那么就称 xxyy 的因数。
  • 如果 xxyy 的因数,且 xyx\neq y,那么就称 xxyy 的真因数。

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

输入格式

输入第一行为两个整数 nnmm

接下来 nn 行,每行有 mm 个数,第 ii 行、第 jj 列上的元素是 ai,ja_{i,j}

输出格式

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

样例

3 3
1 2 3
5 4 6
9 8 24
5

样例 1 说明

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

数据范围

对于 60%60\% 的数据:1n,m101\le n,m \le 10

对于 100%100\% 的数据:1n,m,ai,j10001\le n,m,a_{i,j} \le 1000