鲁道夫要去拜访伯纳德,他决定乘坐地铁去见他。可以在接受两枚硬币的机器上购买门票,硬币的总和不超过 $$$k$$$。
鲁道夫有两个装有硬币的口袋。左边口袋里有$$$n$$$硬币,面额为$$$b_1、b_2、\dots、b_n$$$。右侧口袋里有 $$$m$$$ 硬币,面额为 $$$c_1、c_2、\dots、c_m$$$。他想从左口袋中恰好选择一枚硬币,并从右口袋中恰好选择一枚硬币(总共两枚硬币)。
帮助 Rudolf 确定有多少种方法来选择索引 $$$f$$$ 和 $$$s$$$ 使得 $$$b_f + c_s \le k$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是每个测试用例的描述。
每个测试用例的第一行包含三个自然数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m \le 100, 1 \le k \le 2000$$$)——分别是左右口袋中的硬币数量,以及柜台支付的两枚硬币的最大和。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_i$$$ ($$$1 \le b_i \le 1000$$$) — 左口袋中硬币的面额。
每个测试用例的第三行包含 $$$m$$$ 整数 $$$c_i$$$ ($$$1 \le c_i \le 1000$$$) — 右侧口袋中硬币的面额。
输出
对于每个测试用例,输出一个整数 - 鲁道夫可以选择两枚硬币的方式数,从每个口袋中取出一枚,以使硬币的总和不超过 $$$k$$$。
示例
输入 #1
4 4 4 8 1 5 10 14 2 1 8 1 2 3 4 4 8 1 2 3 4 2 7 1 1 1 1 2 7 3 4 2000 1 1 1 1 1 1 1
输出 #1
6 0 4 12
注意
请注意,这些对表示数组中硬币的索引,而不是它们的面额。
在第一个测试用例中,Rudolf 可以选择以下硬币对:$$$[1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4]$$$。
在第二个测试用例中,Rudolf 无法以任何方式从每个口袋中选择一枚硬币,因为第一个和第二个数组中的任何两个元素的总和将超过 $$$k=4$$$ 的值。
在第三个测试用例中,Rudolf 可以选择:$$$[1, 1], [2, 1], [3, 1], [4, 1]$$$。
在第四个测试用例中,鲁道夫可以从左口袋中选择任何硬币,从右口袋中选择任何硬币。