Count the X Shapes in a Binary Matrix

You are given an \(n \times n\) binary matrix consisting of 0s and 1s. Your task is to count the number of distinct X shapes in the matrix. An X shape is defined as a connected block of ones that forms an X pattern.

An X shape is composed of two diagonals: a left diagonal (\(\backslash\)) and a right diagonal (\(/\)). Both diagonals must be of equal length, and the pattern must be centrally symmetric. In addition, the length of each diagonal (denoted by \(L\)) must be greater than 1.

Formally, for a given center cell \((i,j)\) and an integer arm length \(r\) (where \(r \ge 2\)), the cells that form the X shape are:

[ {(i-k, j-k), (i-k, j+k), (i+k, j-k), (i+k, j+k) \mid k = 0, 1, \ldots, r-1} ]

An X is valid if all of these positions contain the value 1.

For example:

Input:
101
010
101
Output: 1

Input:
1001
0110
0110
1001
Output: 2

Input:
10001
01010
00100
01010
00001
Output: 1

inputFormat

The first line contains an integer \(n\) representing the size of the matrix. The following \(n\) lines each contain a string of length \(n\) consisting of characters '0' and '1', representing the matrix rows.

Example:

3
101
010
101

outputFormat

Output a single integer representing the number of valid X shapes in the given matrix.

sample

3
101
010
101

1