GcdMatrix

You are given a matrix $A$ of integers with $N$ lines and $M$ columns, each indexed from $1$.

A submatrix of matrix $A$ is a matrix which consists of all elements which come from the rows with indices $x_1, x_1+1, \dots, x_2$ and the columns with indices $y_1, y_1+1, \dots, y_2$ of matrix $A$, where $1 \leq x_1 \leq x_2 \leq N$ and $1 \leq y_1 \leq y_2 \leq M$ are the edge rows and columns of the submatrix.

Task

Compute the numbers of submatrices of $A$ for which the greatest common divisor of their elements is $1$ (the greatest common divisor of a set of numbers is the greatest number which divides each of them without remainder).

Input data

The first line contains two integers integer $N$ and $M$, the numbers of rows and columns of the matrix $A$ respectively.
The next $N$ lines each contain $M$ integers, where the $j^{th}$ element from the $i^{th}$ line of the input represents the matrix element $A[i][j]$ (each dimension being indexed from $1$).

Output data

You need to write a single line with an integer: the numbers of submatrices of $A$ for which the greatest common divisor of their elements is $1$.

Constraints and clarifications

• $1 \leq N , M \leq 800$
• $1 \leq A[i][j] \leq 400$

Example

stdin

2 2
1 2
3 4

stdout

5

Explanations

In the sample case, one example of a submatrix where the greatest common divisor of its elements is $1$ is the whole matrix.