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\)