题目内容

工程师小刘需要评估两个独立传感器采集的数据。传感器 $X$ 记录了 $n$ 个读数 $x_1, x_2, \dots, x_n$，传感器 $Y$ 记录了 $m$ 个读数 $y_1, y_2, \dots, y_m$。对于任意来自 $X$ 的读数 $x_i$ 和来自 $Y$ 的读数 $y_j$，定义复合指标为其乘积 $x_i \times y_j$。给定一个预设的质量阈值 $K$，若 $x_i \times y_j \ge K$，则称该配对 $(i, j)$ 合格。你的任务是统计所有 $n \times m$ 个配对中合格配对的总数。

由于可能涉及大量传感器数据和多组测试，你需要高效地计算出结果。

约束条件：

• 测试组数 $T$：1 ≤ T ≤ 10^5
• 每组读数序列长度 $n, m$：n, m ≥ 1，且所有测试中 $n + m$ 的总和 ≤ 2 × 10^5
• 阈值 $K$：0 ≤ K ≤ 10^18
• 每个读数 $x_i, y_j$：0 ≤ x_i, y_j ≤ 10^9，均为整数。

输入描述

第一行包含一个整数 T (1 ≤ T ≤ 10^5)，表示测试用例的个数。接下来每组测试用例的数据按以下格式给出：

• 第一行包含三个整数 n、m 和 K（n, m ≥ 1；0 ≤ K ≤ 10^18；所有测试中 n+m 之和 ≤ 2 × 10^5）。
• 第二行包含 n 个整数 $x_1, x_2, \dots, x_n$，每个 $x_i$ 满足 0 ≤ x_i ≤ 10^9。
• 第三行包含 m 个整数 $y_1, y_2, \dots, y_m$，每个 $y_j$ 满足 0 ≤ y_j ≤ 10^9。

输出描述

对于每组测试用例，输出一行一个整数，表示满足 $x_i \times y_j \ge K$ 的配对数量。

样例1

输入

1
2 2 5
2 3
1 4

输出

2

说明

对于传感器 $X$ 的读数 2，需要 $Y$ 的读数满足 $y_j \ge \lceil 5/2 \rceil = 3$，$Y$ 中仅有 4 满足，贡献 1 对；对于读数 3，需要 $y_j \ge \lceil 5/3 \rceil = 2$，$Y$ 中仅有 4 满足，贡献 1 对。

合计 2 对合格配对。

样例2

输入

1
2 3 0
0 5
2 7 0

输出

6

说明

当 $K = 0$ 时，任意两个非负整数的乘积都满足 $\ge 0$。传感器 $X$ 有 2 个读数，传感器 $Y$ 有 3 个读数，共 $2 \times 3 = 6$ 个配对。

即使存在 0 值（例如 $x_1 = 0$ 或 $y_3 = 0$），乘积为 $0$，依然满足 $0 \ge 0$，因此全部 6 对均合格。

样例3

输入

1
3 3 7
0 3 8
0 2 4

输出

3

说明

对于 $x_1 = 0$，由于 $K = 7 > 0$，所有包含该读数的乘积恒为 $0$，不满足 $\ge 7$，贡献 0。

对于 $x_2 = 3$，需要 $y_j \ge \lceil 7/3 \rceil = 3$，$Y$ 中仅有 4 满足，贡献 1。

对于 $x_3 = 8$，需要 $y_j \ge \lceil 7/8 \rceil = 1$，$Y$ 中有 2 和 4 满足，贡献 2。

总计 3 对合格配对。

样例4

输入

1
1 1 1000000000000000000
1000000000
1000000000

输出

1

说明

本样例测试极端阈值。传感器 $X$ 的读数 $x_1 = 10^9$，传感器 $Y$ 的读数 $y_1 = 10^9$，乘积为 $x_1 \times y_1 = 10^{18}$。

给定阈值 $K = 10^{18}$，由于 $10^{18} \ge 10^{18}$ 成立，该配对合格，总数为 1。