8686: Matrix and GCD

Given an $n\times m$ Matrix $M$ where each integer $i$ $(1\le i\le nm)$ appears exactly once in $M$. Let the value of a submatrix of $M$ as the greatest common divisor (GCD) of all the entries among the submatrix, you need to determine the sum of the values for all continuous submatrices of $M$.

The first line contains two integers $n$ and $m$ $(1\le n,m\le 1000)$.
Following $n$ lines each contains $m$ integers Mi,jM_{i,j}Mi,j (1≤Mi,j≤nm)(1\le M_{i,j} \le nm)(1≤Mi,j≤nm), denoting the given matrix.
It is guaranteed that each integer $i$ $(1\le i\le nm)$ appears exactly once in $M$.

Output one line containing one integer, denoting the answer.

3 3
1 2 3
4 5 6
7 8 9

78