Problem Statement

There is a string $S$ consisting of ( and ).

Taro and Jiro will play the following game using this string.

Taro goes first and Jiro goes second; they alternately choose and perform one of the following three types of operations:

• Delete the first character of $S$.
• Delete the last character of $S$.
• Declare termination.

The game ends when the length of $S$ becomes exactly $K$, or when either player declares termination. At the end of the game, if $S$ is a correct bracket sequence, Jiro wins; otherwise, Taro wins.

Given $S$ before the game starts, determine the winner when both players act optimally.

You are given $T$ test cases. Solve each of them.

What is a correct bracket sequence? A correct bracket sequence is a string that can be reduced to an empty string by repeating the operation of deleting a substring () zero or more times.

Constraints

• $1 \le T \le 10^5$
• $1 \le K < |S| \le 10^6$
• $S$ is a string consisting of ( and ).
• $T$ and $K$ are integers.
• The sum of $|S|$ over all test cases is at most $10^6$.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

S
K

Output

For each test case, print First if Taro wins, and Second if Jiro wins.