Counting Heatwave Patterns in Temperature Grids

You are given one or more datasets representing temperature grids. Each dataset begins with an integer N indicating the size of the grid (an N×N matrix), followed by N lines, each containing N space-separated integers. A dataset with a starting value of 0 indicates the end of input.

A heatwave is defined as a sequence of three or more consecutive grid cells having the same temperature. Consecutive cells may be aligned horizontally, vertically, or diagonally (both left and right diagonals).

Your task is to count the number of distinct heatwave patterns in each temperature grid. When checking for a pattern, consider sequences in each of the four directions: horizontal, vertical, diagonal down-right, and diagonal down-left.

In formal terms, if a cell at position \( (i,j) \) initiates a sequence in direction \( (d_i,d_j) \) and if for some \( k \ge 0 \) we have \[ \text{grid}[i+k\cdot d_i][j+k\cdot d_j] = T, \quad\text{for}\; k=0,1,2,\dots, L-1, \] where \( L \ge 3 \) and \( T \) is a constant temperature, then it qualifies as a heatwave pattern.

For each dataset provided, output the number of heatwave patterns found in its grid.

inputFormat

The input is read from standard input (stdin) and consists of several datasets. Each dataset starts with a single integer N (\(1 \le N\le 1000\)) indicating the grid size. This is followed by N lines, each containing N space-separated integers representing the grid temperatures. The input terminates with a line containing the integer 0.

outputFormat

For each dataset, output a single integer on its own line representing the number of heatwave patterns found in the grid.

## sample

3
30 30 30
25 30 25
30 25 30
0

3

</p>