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