Read problems statements in Mandarin Chinese and Russian as well.

Chef has recently learnt about sequences of parentheses. These are special sequences that contain only the characters '(' and ')'.
A regular parentheses sequence follows the following definition:

An empty sequence is regular
If S is a regular sequence, then (S) is also regular
If A and B represent two regular sequences, then their concatenation AB is also regular.
Therefore, the sequences (), ()() and (())() are regular, while ()(, ) and ))() are non-regular.
Now, you need to find the longest subsequence of the given sequence which is non-regular. Amongst all such distinct answers, output the lexicographically K^{th} amongst them. If the number of distinct subsequences with maximum length is less than K, please output -1 instead.

------ Input: ------

The first line contains a single integer T, denoting the number of test cases to follow.

Each of the test cases have exactly two lines, the first contains the parentheses sequence and the second contains the value of K.

------ Output: ------

Output exactly T lines, each containing answer to the corresponding query.

------ Constraints: ------

$1 ≤ T ≤ 10$
$1 ≤ |S| ≤ 10^{5}$
$1 ≤ K ≤ 10^{9}$

------ Notes: ------

$A subsequence of a given sequence A is a non-empty sequence obtained by removing zero or more characters from A. It does not need to be contiguous.$
$A sequence A is called different from another sequence B, if there exists an integer k, such that 1 ≤ k ≤ N (N is the length of both sequences), and A_{k} != B_{k}.$
$Consider two different N-length sequences, A and B. Let k be the smallest integer such that A[k] != B[k] and 1 ≤ k ≤ N. If A[k] < B[k], then A is said to be lexicographically smaller than B, and vice-versa.$

----- Sample Input 1 ------
5
()
2
(()
1
(()
2
(())
2
(())
3
----- Sample Output 1 ------
)
(()
-1
())
-1

----- explanation 1 ------
Case 1:
Following are the subsequences:

Length Subsequence Regular/Non-Regular

1 ( Non-regular
1 ) Non-regular
2 () Regular

There are two non-regular subsequences of equal length:'(' and ')'.
We are asked for the lexicographically 2nd, so output should be ')'.
Case 2:
Following are the subsequences:

Length Subsequence Regular/Non-Regular
1 ( Non-Regular
1 ) Non-Regular
2 (( Non-Regular
2 () Regular
3 (() Non-Regular

In this case, there are non-regular subsequences of lengths 1, 2, and 3. But, as 3 is the maximum among these, we choose, (().
Case 3:
The string is same as Case 2, and we realize that there is only one subsequence of the maximum length 3, thus we must output -1.
Case 4:
We can find that following subsequences have maximum length and are non-regular.

Length Subsequence
3 ())
3 (()

In lexicographical order, we have following subsequences: [ ((), ()) ]
The query asks for 2nd subsequence, thus the required output is ()).
Case 5:
This is the same sequence as last case, and we know that there are exactly 2 distinct subsequences of maximum length. Thus, answer should be -1.

见题面

见题面