You are given an array containing N distinct integers. You perform the following operations on this array:

• For each pair of integers, you find the absolute difference D between those integers and insert D into the array (if it was not already present in the array).
• You repeat task 1 until the array becomes constant. This implies that the absolute difference between any two elements in the array is also an element present in the array.

Write a program to find the $K^{th}$ largest element of the array after all the operations have been performed. If there is no such element, print -1.

Input format

• First line: T (Number of test cases)
• First line in each test case: N
• Second line in each test case: N space-separated integer (denoting the elements of the array)
• Third line in each test case: K

Output format

For each test case, print the $K^{th}$ largest element of the array. If there is no such element print -1.

Constraints

$1 \le T \le 100$
$1 \le N,K \le 10000$
$1 \le$ Element of the array $\le 100000$