NSIT ACM SAARC Prelims

Amit is getting bored. He has an LED box that can be represented as a rectangular grid of sides, N × M. The LEDs work only in two modes, "ON" or "OFF".

He decides to design a pattern with the LEDs. However, the LED box is peculiar.

In one move, Amit can choose a sub-rectangle of exactly R rows and C columns and toggle the LEDs in that sub-rectangle.

Formally, all LEDs in the subrectangle, which are "ON" change to "OFF" while LEDs that are "OFF" change to the "ON".

Your task is to help Amit determine the minimum number of moves required to make the pattern or output -1 if it is not possible.

Initially, all LEDs are off.

T <= 1000

1 <= N, M <= 300

1 <= R <= N

1 <= C <= M

Input

First line consists of the number of test cases, T.

Then follows T test cases each with the first line N, M, R, C.

Then follows, N lines with exactly M characters denoting the state of the LEDs in the desired pattern.

• 0 - denotes OFF.
• 1 - denotes ON.

Output

T lines each containing the minimum number of moves to establish the pattern or -1 if it is not possible.

Example

Input:
3
3 3 1 1
010
111
011
4 4 2 1
0111
1101
0110
1101
3 4 2 2
0110
0110
0000

Output:
6
-1
1