【题目背景】

比赛已经结束，但主办方不想立即公布所有题目的分数。他们希望只公开尽量少的单题成绩，让观众看到一种“恰好还有若干人可能夺冠”的局面。

【题目描述】

一场比赛有$𝑁$名选手，编号为 $0$ 到 $𝑁−1$，共有 $𝑀$道题。每道题的满分均为 $𝐾$，其中$1≤𝐾≤2$。

选手 $𝑖$ 在题目$𝑗$上的真实得分为$𝑎_{𝑖,𝑗}$，且$0≤𝑎_{𝑖,𝑗} ≤𝐾$。比赛开始时，观众尚不知道任何一项单题得分。

主办方可以选择若干个位置$(𝑖,𝑗)$，公开这些位置的真实得分 $𝑎_{𝑖,𝑗}$。每个位置至多公开一次，公开一个位置计作公开一个单题分数。即使公开的分数为 0，也需要计入公开数量。

对于一个尚未公开的位置，观众只知道该位置可能是 0 到 𝐾 之间的任意整数。观众的猜测不需要与该位置的真实得分$𝑎_{𝑖,𝑗}$一致。

在一种补全方案中，为所有尚未公开的位置各指定一个 0 到 𝐾 之间的整数。选手的总分为其$𝑀$道题分数之和。总分较高者排名更高；若两名选手总分相同，则编号较小者排名更高。

如果存在至少一种与全部已公开信息相符的补全方案，使选手$𝑥$排名第一，则称选手 $𝑥$ 是一名候选冠军。不同候选冠军可以对应不同的补全方案，不要求存在一种方案使所有候选冠军同时排名第一。

主办方希望通过公开若干个真实单题分数，使候选冠军的人数恰好为 $𝑅$。

请计算主办方至少需要公开多少个单题分数。如果无法做到，输出 -1。

本题包含多组互相独立的测试数据。

【输入格式】

第一行包含一个整数 𝑇，表示测试数据的组数。

接下来依次输入 𝑇 组测试数据。对于每组测试数据：

• 第一行包含四个整数 𝑁,𝑀,𝐾,𝑅，分别表示选手数、题目数、每题满分和目标候选冠军人数；

• 接下来 𝑁 行，每行包含 𝑀 个整数。第 𝑖 行的第 𝑗 个整数表示 $𝑎_{𝑖,𝑗}$。

选手和题目均从 0 开始编号，但输入矩阵的第一行、第一列分别对应选手 0 和题目 0。

【输出格式】

输出 𝑇 行。 第 𝑖 行包含一个整数，表示第 𝑖 组测试数据中至少需要公开的单题分数数量；如果 无法做到，输出 -1。

4
3 2 2 2
2 0
0 0
0 0
2 1 1 1
1
1
4 3 2 4
0 0 0
1 0 1
2 0 0
1 1 0
3 2 2 1
2 2
2 2
2 2

2
1
0
2

【样例1解释】

对于第一组测试，可以公开选手 0 在题目 0 上的 2 分，以及选手 2 的一个 0 分。

此时选手 0 的已知总分为 2。选手 2 的最高可能总分为 2，即使与选手 0 同分，也会因为编号更大而排名更低，因此选手 2 不再可能夺冠。选手 1 仍可能得到 4 分，所以候选冠军恰好为选手 0 和选手 1。可以证明只公开一个分数无法做到，因此答案为 2。

对于第二组测试，只需公开选手 0 的 1 分。选手 1 的最高可能总分也是 1，但同分时选手 0 排名更高，因此只有选手 0 可能夺冠，答案为 1。

对于第三组测试，目标人数等于选手总数。最初每名选手都可能在某种补全方案中取得最高分，因此不需要公开任何分数，答案为 0。

对于第四组测试，公开选手 0 的两个 2 分后，其已知总分为 4。其他选手的最高可能总分也只有 4，同分时均排在选手 0 之后，因此候选冠军只有选手 0。只公开一个分 数时仍有其他选手可能取得更高总分，所以答案为 2。

【数据范围】

对于所有测试数据：

$1≤𝑇 ≤150000，2≤𝑁 ≤300000，1≤𝑀 ≤300000，1≤ 𝐾 ≤2，1≤𝑅≤𝑁，0≤𝑎_{𝑖,𝑗} ≤𝐾$。

每组测试数据满足 $𝑁×𝑀≤300000$。

每个评测点内的所有测试数据满足 $∑(𝑁×𝑀)≤300000$。