Distinct Islands Counting

In this problem, you are given a two-dimensional grid of integers where each cell is either 0 (water) or 1 (land). An island is a group of connected 1s (connected horizontally or vertically). Two islands are considered to be the same if one can be translated (without rotation or reflection) to match the other. Your task is to count the number of distinct islands in each test case.

The shape of an island is determined by the relative positions of its cells when traversed using a depth-first search (DFS) starting from a given starting point. A unique signature for an island can be captured using the sequence of moves taken during the DFS, including markers for backtracking.

Note: Islands are distinct if their DFS signatures are different.

inputFormat

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

T
M N
row1 (N integers separated by space)
row2
...
rowM
... (repeat for each test case)

Where T is the number of test cases. For each test case, the first line contains two integers M and N representing the grid dimensions, followed by M lines each containing N integers (0 or 1).

outputFormat

For each test case, output the number of distinct islands on a separate line to standard output (stdout).

## sample

1
3 3
1 1 0
0 1 0
1 0 0

2

</p>