GcdMatrix

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

You are given a matrix AA of integers with NN lines and MM columns, each indexed from 11.

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

Task

Compute the numbers of submatrices of AA for which the greatest common divisor of their elements is 11 (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 NN and MM, the numbers of rows and columns of the matrix AA respectively.
The next NN lines each contain MM integers, where the jthj^{th} element from the ithi^{th} line of the input represents the matrix element A[i][j]A[i][j] (each dimension being indexed from 11).

Output data

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

Constraints and clarifications

  • 1N,M8001 \leq N , M \leq 800
  • 1A[i][j]4001 \leq A[i][j] \leq 400
# Points Constraints
1 10 N,M<16N, M < 16
2 25 N,M<64N, M < 64
3 25 N,M<128N , M < 128 and max{A[i][j]}<64\max\{A[i][j]\} < 64
4 25 max{A[i][j]}<4\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 11 is the whole matrix.

Log in or sign up to be able to send submissions!