Given a set of N digits, find the $k^{th}$ smallest number that can be formed using them such that the sum of its digits is prime. If the answer does not exists or is greater than $10^{18}$ print 1.

Input:
First line consists of a single integer T denoting the number of test cases.
Second line consists of a single integer denoting N.
Third line consists of N space separated numbers denoting the set of digits. Fourth line consists of a single integer denoting k.

Output: Print the required answer in a new line for each test case.

Constraints:
$1 \le N \le 9$
$1 \le k \le 10^{18}$