Counting Collinear Letter Lines

Given an \(n \times n\) grid, each cell either contains a single uppercase letter or is empty. No letter appears more than once in the grid. A line is said to be valid if it passes through the centers of at least three cells that contain a letter. Note that the center of a cell in row \(i\) and column \(j\) can be represented by the point \((i, j)\) (assuming rows and columns are 1-indexed).

Your task is to count the number of distinct lines that pass through the centers of at least three letter-containing cells. Two lines are considered the same if they have the same line equation.

Note: A line determined by more than three points is counted only once.

inputFormat

The first line contains a single integer \(n\) (the size of the grid).\nbsp;

Then follow \(n\) lines, each containing exactly \(n\) characters. Each character is either an uppercase letter (A-Z) indicating that the cell contains that letter or a dot '.' indicating an empty cell.

outputFormat

Output a single integer, the number of distinct lines that pass through the centers of at least three letter-containing cells.

sample

3
A..
.B.
..C

1