Minimum Operations to Transform the Grid

You are given two grids of size (N \times M): an initial grid (G) and a target grid (T). Each cell in both grids contains a positive integer. You are allowed to perform the following operation any number of times:

Select any 2 (\times) 2 subgrid (i.e. four adjacent cells) in (G) and multiply each element in that subgrid by an integer (d) where (d > 1). The goal is to transform (G) into (T) using the minimum number of operations. If it is impossible to achieve (T) exactly from (G) by such operations, output (-1).

Important: In every operation, all four cells in the chosen subgrid are multiplied by the same factor. The transformation must occur exactly, meaning that after all operations, every cell (G_{ij}) must equal (T_{ij}).

inputFormat

The input is read from standard input. The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (N) and (M) separated by a space, which indicate the number of rows and columns of the grid. Next, there are (N) lines each with (M) space-separated integers describing the initial grid (G). This is followed by another (N) lines each containing (M) space-separated integers representing the target grid (T).

outputFormat

For each test case, output a single line containing the minimum number of operations needed to transform (G) into (T). If it is impossible, output (-1).## sample

1
2 2
1 1
1 2
2 2
2 4

1