AT_arc209_a [ARC209A] Bracket Game

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.

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 $

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

### Sample Explanation 1 For the first test case, here is an example of how the game might proceed: - Before the game starts, $ S $ is `(()())`. - Taro deletes the first character of $ S $ , resulting in `()())`. - Next, Jiro deletes the last character of $ S $ , resulting in `()()`. - Next, Taro deletes the last character of $ S $ , resulting in `()(`. - Next, Jiro deletes the last character of $ S $ , resulting in `()`, and the length of $ S $ becomes $ K=2 $ , so the game ends. - The final $ S $ is a correct bracket sequence, so Jiro wins. In the third test case, for example, Taro can win by declaring termination on the first turn. ### 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 $ .