The country of BitLand is divided into N districts, and these districts are arranged in a circle: 1, 2, 3, ..., N, where i and i+1 are adjacent for all 1 ≤ i ≤ N-1, and also 1 and N are adjacent. It is given that N = o_{1} * o_{2}, where o_{1} and o_{2} are odd integers.

There are only 2 political parties in BitLand: the Zeros and the Ones. There was an election, in which each district chose it's representative who is either a Zero or a One. We know this data. i.e. for each of the N districts, we know whether their representative is a Zero or a One.

The N districts should be partitioned into o_{1} states, where each state consists of o_{2} consecutive districts.

For example, if o_{1} = 5 and o_{2}=3, then N=15, and {1,2,3} would be a valid state. {2,3,4}, {13,14,15}, {14,15,1}, {15,1,2} are other examples of valid states. But {3,5,6} is not a valid state, because the districts are not consecutive.

A state gets a One Governor if, among all the o_{2} district representatives belonging to it, there are more One district representatives than Zero representatives. And it gets a Governor who is from the Zero party, if the majority of its district representatives are from the Zero party. And because o_{2} is odd, there will be no ties.

The President of BitLand will be a One if the majority of the o_{1} state Governors are Ones. Otherwise, the President will be from the Zero party.

But the state boundaries have not been fixed yet. Given just the district-wise data (i.e. whether each district's representative is a Zero or a One), you need to find if there is a way to partition them into states such that the President is a One.

------ Input ------

The first line contains one integer, T, which is the number of testcases.
The first line of each testcase contains two space separated integers, o_{1} and o_{2}, which are the number of states, and number of districts in each state, respectively.

The next line of each testcase contains N = o_{1} * o_{2} space separated integers: d_{1}, d_{2}, .., d_{N}. If d_{i} is 1, then it signifies that District i has chosen a One representative. If d_{i} is 0, then they have a Zero representative.

------ Output ------

Each testcase should be in a new line, and should contain 1, if the President can be a One, and 0 otherwise.

------ Constraints ------

For all subtasks you may assume that:
1 ≤ T ≤ 100$o_{1},o_{2} will be odd positive integers.$

$1 ≤ Summation of o_{1}*o_{2} over all testcases ≤ 10^{6}$
$0 ≤ d_{i} ≤ 1$

Subtask 1: For 10% of the score,

$1 ≤ Summation of o_{1}*o_{2} over all testcases ≤ 10^{4}$

Subtask 2: For further 20% of the score,
1 ≤ o_{1} ≤ 10^{4}
1 ≤ o_{2} ≤ 10^{2}

Subtask 3: For further 70% of the score,
No further constraints.$

----- Sample Input 1 ------
4
5 1
1 0 0 1 1
3 3
0 0 1 1 0 1 1 0 0
3 3
1 1 1 0 1 0 0 1 0
3 3
1 0 0 1 1 0 1 0 0
----- Sample Output 1 ------
1
1
1
0
----- explanation 1 ------

In the first testcase, each state should have only 1 district, and hence, there is no actual choice in constructing the states. There will be three One Governors, and two Zero Governors, and hence the President will be a One.

In the second testcase, each of the three states should should have 3 districts each. Consider the following partitioning of the districts into states: {2,3,4}, {5,6,7} and {8,9,1}. So, the first state consists of the districts {2,3,4}, and the representatives of these correspond to {0,1,1}. The majority is One, and hence the first state will have a One Governor. The representatives corresponding to the second state are {0,1,1}, and so again, this will have a One Governor. The third state has representatives {0,0,0}, and hence will have a Zero Governor. On the whole, there are two One Governors, and one Zero Governor, and hence the President will be a One. And since there is a way to partition the districts into states, in which the President is a One, the answer is 1.

In the third testcase, each of the three states should should have 3 districts each. Consider the following partitioning of the districts into states: {3,4,5}, {6,7,8} and {9,1,2}. So, the first state consists of the districts {3,4,5}, and the representatives of these correspond to {1,0,1}. The majority is One, and hence the first state will have a One Governor. The representatives corresponding to the second state are {0,0,1}, and since the majority is Zero, this will have a Zero Governor. The third state has representatives {0,1,1}, and as Ones are in majority, this will have a One Governor. On the whole, there are two One Governors, and one Zero Governor, and hence the President will be a One. And since there is a way to partition the districts into states, in which the President is a One, the answer is 1.

In the fourth testcase, you can check that no matter how you construct the states, the President cannot be a One. Hence, the answer is 0.

见题面

见题面