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$

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

5 | 15 | No additional constraints. |

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