To Eat or Be Eaten

Interview

Time limit1sMemory limit256 MB

Summary

Count pairs where an A creature is strictly larger than a B creature, given two lists of sizes.

Level: Medium4 of 10
Topics: Sorting, Two pointers, Binary search, Array
Solved: No attempts yet

Problem

In the deep sea live two kinds of creatures, A and B. An A can eat a B only if the B is strictly smaller than that A.

For example, if the sizes of A are {8, 1, 7, 3, 1} and the sizes of B are {3, 6, 1}, then the pairs in which A can eat B are 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, and 3-1 — seven pairs in total.

Given the sizes of A and B, write a program that counts how many pairs (A, B) satisfy that A's size is greater than B's size.

Input

The first line contains the number of test cases $T$ .

For each test case, the first line contains the count of A, $N$ , and the count of B, $M$ , separated by a space. The second line contains the $N$ sizes of A, and the third line contains the $M$ sizes of B, each separated by spaces. Every size is a positive integer. ( $1 \le N, M \le 20{,}000$ )

Output

For each test case, print on its own line the number of pairs in which A's size is greater than B's size.

Examples1

Example 1

Input

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

Expected output

7
1