题目内容

给定两个整数序列 $a$（长度为 $n$）与 $b$（长度为$m$）。

构造一个 $n \times m$的矩阵$C$，其中$C_{i,j} = a_i \cdot b_j$。

给定阈值$k$，请你统计矩阵中有多少个元素满足 $C_{i,j} \ge k$。

输入描述

每个测试文件均包含多组测试数据。

• 第一行输入一个整数 $T\ (1 \le T \le 10^5)$表示数据组数。

• 每组测试数据描述如下：

  • 第一行输入三个整数 $n, m, k\ (1 \le n, m \le 2 \times 10^5,\ 0 \le k \le 10^{18})$；
  • 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n\ (0 \le a_i \le 10^9)$；
  • 第三行输入 $m$ 个整数 $b_1, b_2, \dots, b_m\ (0 \le b_j \le 10^9)$。

保证所有测试中$n + m$ 的总和不超过 $2 \times 10^5$。

输出描述

对每组数据输出一行，一个整数，表示满足 $a_i \cdot b_j \ge k$ 的矩阵元素个数

样例1

输入

3
3 3 6
1 2 3
2 3 4
2 4 1
0 5
0 0 1 10
2 3 1
1 1
1 1 1

输出

5
2
6

说明

• 第一组：矩阵为

$\begin{bmatrix} 1 \cdot 2 & 1 \cdot 3 & 1 \cdot 4 \\ 2 \cdot 2 & 2 \cdot 3 & 2 \cdot 4 \\ 3 \cdot 2 & 3 \cdot 3 & 3 \cdot 4 \end{bmatrix} = \begin{bmatrix} 2 & 3 & 4 \\ 4 & 6 & 8 \\ 6 & 9 & 12 \end{bmatrix}$

其中 $\ge 6$的元素共有 $5$ 个。

• 第二组：仅 $(1,5)$ 与 $(10,5)$的乘积 $\ge 1$，答案为 $2$。
• 第三组：所有条目均为 $1$，共有 $2 \times 3 = 6$ 个满足 $k=1$