# GcdMatrix

Time limit: 1.2s Memory limit: 128MB Input: Output:

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.

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$
# Points Constraints
1 10 $N, M < 16$
2 25 $N, M < 64$
3 25 $N , M < 128$ and $\max\{A[i][j]\} < 64$
4 25 $\max\{A[i][j]\} < 4$

## 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.