在数论中，算术基本定理（也称为唯一分解定理）指出，每个大于 1 的整数要么本身是一个素数，要么可以表示为素数的乘积，且这种表示是唯一的。例如，$720 = 2^4 \times 3^2 \times 5^1$。

根据唯一分解定理，我们可以将任何整数 $x$ 表示为： $$x = 2^{e(x,2)} \times 3^{e(x,3)} \times 5^{e(x,5)} \times \dots \times p_i^{e(x,p_i)} \times \dots$$ 其中 $p_i$ 是第 $i$ 小的素数。现在，我们定义一种比较两个整数 $x$ 和 $y$ ($x, y \ge 2$) 的不同方法：

• 当 $x = y$ 时，我们认为 $x$ 等于 $y$。
• 当 $x \neq y$ 时，找到最小的正整数 $i$，使得对于所有的 $j = 1, 2, \dots, i - 1$ 都有 $e(x, p_j) = e(y, p_j)$，且 $e(x, p_i) \neq e(y, p_i)$。此时，当且仅当 $e(x, p_i) < e(y, p_i)$ 时，我们认为 $x$ 小于 $y$，否则我们认为 $x$ 大于 $y$。

给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$ 和 $m$ 个正整数 $b_1, b_2, \dots, b_m$。考虑所有 $n \times m$ 个可能的两两乘积 $a_i \times b_j$ ($1 \le i \le n, 1 \le j \le m$)，并按照上述比较规则将它们按非递减顺序排列。你的任务是找出该列表中的第 $k$ 个数。注意，列表中的元素编号从 $1$ 到 $n \times m$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 2000$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m \le 10^5, 1 \le k \le n \times m$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le i \le n, 2 \le a_i \le 10^6$)。 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le i \le m, 2 \le b_i \le 10^6$)。

保证所有测试用例中 $n$ 的总和不超过 $10^5$，且所有测试用例中 $m$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示列表中的第 $k$ 个数。

样例

输入 1

1
3 3 6
7 5 7
3 2 7

输出 1

15

说明

样例测试中的列表为 $[49, 49, 35, 21, 21, 15, 14, 14, 10]$。