该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

银河历 4582 年，银河联邦议会发起首届「​群星算法竞技赛​」，旨在以文明的计算力与战略规划能力决出名次，而非诉诸舰队与战争。

来自银河各处的 n 个星际文明参赛，每个文明派出一名首席科学官作为代表。你是人类联邦的首席科学家灰风（编号 1）。

竞技规则沿用银河标准 ICPC 范式：

• 每破解一道​远古遗构算法谜题​，获得 ​1 点科技积分​。
• 同时累积​时序损耗​：从竞赛开始到破解成功的银河分钟数。
• 排行榜优先级：​科技积分高者靠前；积分相同，时序损耗少者靠前​。
• 若积分与时序损耗完全一致，​人类联邦（灰风）优先排名靠前​。

设定

• 共 m 道远古谜题，由失落帝国遗留的 AI 系统随机生成。
• 竞赛总时长：h 银河分钟（超过即强制终止）。
• 超级预言 AI「​肃正协议​」已预演所有文明的解谜效率：
  • $(t_{i,j})$：第 i 号文明破解第 j 道谜题所需的银河分钟数。

输入格式

第一行包含一个整数 $t(1≤t≤10^3)$——测试用例的数量。

然后遵循测试用例的描述。

每个测试用例的第一行包含三个整数 $n，m，h(1≤n⋅m≤2⋅10^5，1≤h≤10^6)$——分别是参赛文明数量、远古谜题数量、赛事总限时银河分钟。

然后是 n 行，每一行包含 m 整数 $(t_{i,j})(1≤(t_{i,j})≤10^6)$——第 $i$ 个文明破译第 $j$ 道谜题所需要的时间（单位：分钟）。

保证所有测试数据的 $n⋅m$ 的总和不超过 $2⋅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 道谜题，获得 1 积分、罚时 90 分钟；第三名文明破译全部谜题，拿到 3 积分但总罚时高达 240 分钟。综合排位后，灰风位列第二名。

第二组赛事中，对灰风与另一文明同为 1 点科技积分、30 分钟时序罚时。按照星际特权规则，同分同罚时情况下鲁道夫优先靠前，最终排名第一名。

第三组赛事仅有灰风一个文明参赛，默认稳居第一位。

第四组赛事中，所有文明均可破译两道谜题，各自时序罚时分别为：灰风 25、异族乙 24、异族丙 26。按罚时升序排位，异族乙第一，灰风位列第二名。

限制

1s, 1024KiB for each test case.