Rudolf and the Another Competition

链接：https://codeforces.com/contest/1846/problem/C
来源：codeforces

时间限制：1 seconds
空间限制：256 megabytes

题目描述

鲁道夫已经报名参加了一个遵循ICPC规则的编程比赛。这个规则的比赛意味着每解决一个问题，参赛者就会得到\(1\)分，同时也会受到相当于从比赛开始到解决该问题的时间的惩罚（罚时）。在最后的排名中，积分最多的参赛者排名靠前，如果积分相同，罚时少的参赛者排名靠前。

总共有\(n\)名参赛者报名参加比赛。鲁道夫是编号为\(1\)的参赛者。已知将有\(m\)个问题被提出。而比赛将持续\(h\)分钟。

一个强大的人工智能预测了数值\(t_{i,j}\)，它代表了\(i\)个参与者解决\(j\)个问题所需的分钟数。

鲁道夫意识到，解决问题的顺序会影响最终结果。例如，如果\(h = 120\)，而解决问题的时间是【\(20, 15, 110\)】，那么如果鲁道夫按照下面这些顺序解决问题：

\({3，1，2}\)，则他将只解决第三个问题，并获得\(1\)积分和\(110\)罚时。

\({1，2，3}\)，那么他将在从开始的\(20\)分钟后解决第一个问题，在\(20+15=35\)分钟后再解决第二个问题，并且他将没有时间解决第三个问题。因此，他将获得\(2\)的积分和\(20+35=55\)的罚时。

\({2，1，3}\)，那么他将在从开始的\(15\)分钟后解决第二个问题，在\(15+20=35\)分钟之后解决第一个问题，并且他将没有时间解决第三个问题。因此，他将获得\(2\)的积分和\(15+35=50\)的罚时。

鲁道夫开始关心，如果每个参赛者根据人工智能的预测，以最佳顺序解决问题，他将在比赛中获得什么名次。假设在积分和罚分相同的情况下，鲁道夫将获得最佳名次。

输入

第一行包含一个整数\(t\)（\(1 \le t \le 10^3\)）--测试案例的数量。

然后按照测试案例的描述。

每个测试案例的第一行包含三个整数\(n, m, h\)（\(1 \le n \cdot m \le 2 \cdot 10^5, 1 \le h \le 10^6\)）--分别是参赛者的数量、问题的数量和比赛的时间。

然后有\(n\)行，每行包含\(m\)个整数\(t_{i, j}\)（\(1 \le t_{i, j} \le 10^6\)）--第\(i\)个参与者解决\(j\)个问题所需的分钟数。

所有测试案例的\(n \cdot m\)之和不超过\(2 \cdot 10^5\)。

输出

对于每个测试案例，输出一个整数--如果所有参与者都按最佳顺序解决问题，那么鲁道夫最后在比赛结束能达到多少名。

样例

输入样例

5
3 3 120
20 15 110
90 90 100
40 40 40
2 1 120
30
30
1 3 120
10 20 30
3 2 27
8 9
10 7
10 8
3 3 15
7 2 6
7 5 4
1 9 8

输出样例

2
1
1
2
1

样例解释

在第一个例子中，鲁道夫将得到\(2\)分和\(50\)分钟的罚时。第二个参与者只解决了一个问题，得到\(1\)分和\(90\)分钟的罚时。而第三位参与者将解决所有的\(3\)个问题，得到\(3\)分和\(240\)分钟的惩罚。因此，鲁道夫将获得第二名。

在第二个例子中，两个参与者都将得到\(1\)分和\(30\)分钟的罚时。在积分相同的情况下，鲁道夫得到的名次更好，所以他将获得第一名。

在第三个例子中，鲁道夫是唯一的参赛者，所以他将获得第一名。

在第四个例子中，所有参与者都能解决两个问题，罚时分别为\(25 = 8 + (8 + 9)\)、\(24 = 7 + (7 + 10)\)和\(26 = 8 + (8 + 10)\)，由于罚时，第二个参与者得到了第一名，而鲁道夫得到了第二名。