Amy와 Aimee, MITIT 클럽의 회원들은 자신들이 발명한 새로운 보드게임을 하고 있습니다!
보드는 $N$개의 칸이 한 줄로 나열되어 있으며, 각 칸은 빨간색, 초록색, 또는 흰색으로 칠해져 있습니다. 플레이어들은 음이 아닌 정수 매개변수 $K$ ($0 \le K \le \min(N-1, 7)$)를 정했습니다. Amy가 먼저 시작하며 번갈아 가며 차례를 갖습니다.
각 차례에 플레이어는 다음 절차에 따라 이동합니다:
흰색 칸들로만 구성된 홀수 개의 칸을 포함하는 부분집합 $S$를 선택합니다. 이때 $S$에 속한 임의의 두 칸 사이의 거리(즉, 좌표의 절댓값 차이)는 $K$를 초과할 수 없습니다.
특히, $S$가 정확히 하나의 흰색 칸을 포함하는 것은 항상 허용되며, $|S|$가 $K + 1$을 초과하는 것은 불가능합니다(물론 $|S|$는 홀수여야 합니다).
빨간색 칸과 초록색 칸이 인접할 수 없다는 조건하에, $S$에 속한 모든 칸을 빨간색으로 칠하거나 모든 칸을 초록색으로 칠합니다. 선택한 $S$에 대해 이 단계를 완료하는 것이 불가능할 수도 있으며, 이 경우 플레이어는 다른 $S$를 선택해야 합니다.
합법적인 이동을 할 수 없는 첫 번째 플레이어가 패배합니다.
Amy가 첫 번째 이동을 하기 전의 보드 상태가 주어지며, 빨간색 칸과 초록색 칸은 인접해 있지 않습니다. 두 플레이어가 최적으로 게임을 할 때 누가 승리할지 결정하십시오.
입력
입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 5 \cdot 10^4$)가 주어집니다.
각 테스트 케이스의 첫 번째 줄에는 $N$과 $K$ ($1 \le N \le 2\cdot 10^5$, $0 \le K \le \min(N-1, 7)$)가 주어집니다.
각 테스트 케이스의 두 번째 줄에는 보드의 초기 상태를 나타내는 $N$개의 문자로 이루어진 문자열이 주어집니다. 각 문자는 R(빨간색), G(초록색), 또는 W(흰색)입니다. R과 G는 인접하지 않음이 보장됩니다.
모든 테스트 케이스에 대한 $N$의 합은 $4 \cdot 10^5$를 초과하지 않습니다.
출력
각 테스트 케이스마다 승리하는 플레이어의 이름을 Amy 또는 Aimee로 출력하십시오.
Scoring
($15$점) $N \le 10$.
($15$점) 초기 상태에서 인접한 두 흰색 칸은 없습니다.
($10$점) 초기 상태가 모두 흰색이고 $K = 0$.
($20$점) $K = 0$.
($40$점) 추가 제약 조건 없음.
예제
입력 1
5 5 4 WWWWW 16 3 RRRRWGGGGGWRRRRR 6 5 WWWWWW 12 0 WWWWRRWGGGWW 13 7 WRRWWGWRWRWWW
출력 1
Amy Aimee Aimee Amy Amy
참고
첫 번째 예제 테스트 케이스에서, Amy는 첫 번째 차례에 보드 전체를 $S$로 선택하고 모두 빨간색으로 칠함으로써 승리할 수 있습니다.
두 번째 예제에서, Amy는 첫 번째 차례에 합법적인 이동을 할 수 없으며 즉시 패배합니다.
세 번째 예제에서, Amy가 첫 번째 이동에서 무엇을 하든, Aimee는 자신의 차례에 항상 보드 전체를 같은 색으로 칠할 수 있어 게임에서 승리합니다.