Between the Mountains

Interview

Time limit1sMemory limit128 MB

Summary

Pick one altitude from each mountain so the absolute difference between the two is as small as possible.

Level: Easy3 of 10
Topics: Two pointers, Sorting
Solved: No attempts yet

Problem

Have you ever ridden a cable car? It is a lot of fun. Our company is building a new cable car line between two high mountains, and you get a free ride if you help design it.

The company wants one platform on each mountain, and the cable runs between those two platforms. The spots suitable for a platform have already been surveyed on both mountains, and the altitude of every spot is recorded.

One engineer pointed out that the line saves a lot of energy when the two platforms sit at the same altitude, or as close to each other as possible. Pick one surveyed spot on each mountain so that the altitude difference between them is as small as possible.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ). Then $2T$ lines follow, two lines per test case.

The two lines of a test case each describe the altitudes of the suitable platform spots on one mountain. Each line starts with the number of recorded altitudes $N$ ( $1 \le N \le 1\,000$ ), followed by the $N$ altitudes recorded on that mountain. Every altitude is an integer between $1$ and $1\,000\,000$ , inclusive.

Output

For each test case, print on a single line the smallest altitude difference you can reach by picking one spot on each mountain.

Examples1

Example 1

Input

2
8 1 3 5 7 9 7 3 1
8 2 4 6 8 10 8 6 2
8 2 3 5 10 9 3 2 1
7 1 2 6 12 13 3 2

Expected output

1
0