The MITIT club regularly hosts "social mixers", which are fun events meant for club members to socialize and take a break from schoolwork, problem writing, or contest organization. Snacks and games are provided. But the games can be a little weird...
Amy and Aimee, members of the MITIT club, are playing a new board game they invented!
The board consists of a row of $N$ squares, each colored either red, green, or white. The players have also agreed on a parameter $K$ (satisfying $0 \le K \le \min(N-1, 7)$), which is a nonnegative integer. Amy goes first and they take turns.
In each turn, the player makes a move following the below procedure:
Choose a subset $S$ with an odd number of squares, all of which are white, such that the distance between any two squares (i.e. the absolute difference of their coordinates) in $S$ does not exceed $K$.
In particular, it is always acceptable for $S$ to have exactly one white cell, and it is never possible for $|S|$ to exceed $K + 1$ (of course, $|S|$ must be odd as well).
Either color all squares in $S$ red or color all of them green, subject to the condition that no red square can ever be adjacent to a green one. It is possible that this step is impossible to complete for some valid choices of $S$; in that case the player is forced to choose $S$ differently.
The first player unable to make a legal move loses.
Given the state of the board before Amy makes her first move, with no red squares adjacent to green squares, determine which player will win if both play optimally.
Input
The input consists of several test cases. The first line contains an integer $T$ ($1 \le T \le 5 \cdot 10^4$): the number of test cases.
The first line of each test case contains $N$ and $K$ ($1 \le N \le 2\cdot 10^5$, $\mathbf{0 \le K \le \min(N-1, 7)}$).
The second line of each test case contains a string of $N$ characters describing the initial state of the board. Each character is either R (red), G (green), or W (white). It is guaranteed that no R is adjacent to a G.
It is guaranteed that the sum of $N$ over all test cases does not exceed $4 \cdot 10^5$.
Output
For each test case, output either Amy or Aimee, indicating the player who will win.
Scoring
- ($15$ points) $N \le 10$.
- ($15$ points) No two white squares are adjacent in the initial state.
- ($10$ points) The initial state is completely white, and $K = 0$.
- ($20$ points) $K = 0$.
- ($40$ points) No additional constraints.
Examples
Input 1
5 5 4 WWWWW 16 3 RRRRWGGGGGWRRRRR 6 5 WWWWWW 12 0 WWWWRRWGGGWW 13 7 WRRWWGWRWRWWW
Output 1
Amy Aimee Aimee Amy Amy
Note
In the first sample test case, Amy can win by choosing $S$ to be the entire board and coloring it all red on her first turn.
In the second sample, Amy cannot make a legal move on her first turn, and she loses immediately.
In the third sample, no matter what Amy does on her first move, Aimee is always able to color the entire board with the same color on her turn, thus winning the game.