Counting Distinct Islands

Given a square grid of size \(N \times N\), each cell is either '0' or '1'. An island is defined as a group of '1's connected horizontally or vertically. Two islands are considered distinct if there exists at least one cell that is present in one island but not in the other (i.e. \(I_1 \setminus I_2 \neq \emptyset\) or \(I_2 \setminus I_1 \neq \emptyset\)).

Your task is to count the number of distinct islands in the grid.

Note: The grid is provided as input where the first line is \(N\) followed by \(N\) lines of grid rows.

inputFormat

The input is read from standard input (stdin) and has the following format:

N
row1
row2
...
rowN

Here, \(N\) is an integer representing the dimensions of the grid, and each row is a string of length \(N\) consisting of characters '0' and '1'.

outputFormat

Output to standard output (stdout) a single integer, which is the number of distinct islands in the grid.

## sample

5
11000
11000
00100
00011
00001

3

</p>