Le club MITIT organise régulièrement des « rencontres sociales », des événements amusants destinés à permettre aux membres du club de socialiser et de faire une pause dans leurs travaux scolaires, la rédaction de problèmes ou l'organisation de concours. Des collations et des jeux sont fournis. Mais les jeux peuvent être un peu étranges...

Amy et Aimee, membres du club MITIT, jouent à un nouveau jeu de plateau qu'elles ont inventé !

Le plateau consiste en une rangée de $N$ cases, chacune colorée en rouge, vert ou blanc. Les joueuses ont également convenu d'un paramètre $K$ (satisfaisant $0 \le K \le \min(N - 1, 7)$), qui est un entier non négatif. Amy commence et elles jouent à tour de rôle.

À chaque tour, la joueuse effectue un coup en suivant la procédure ci-dessous :

1. Choisir un sous-ensemble $S$ avec un nombre impair de cases, toutes blanches, tel que la distance entre deux cases quelconques (c'est-à-dire la différence absolue de leurs coordonnées) dans $S$ n'excède pas $K$. En particulier, il est toujours acceptable que $S$ contienne exactement une case blanche, et il n'est jamais possible que $|S|$ excède $K + 1$ (bien sûr, $|S|$ doit également être impair).

2. Colorier toutes les cases de $S$ en rouge ou en vert, sous la condition qu'aucune case rouge ne puisse jamais être adjacente à une case verte. Il est possible que cette étape soit impossible à réaliser pour certains choix valides de $S$ ; dans ce cas, la joueuse est forcée de choisir $S$ différemment.

La première joueuse incapable d'effectuer un coup légal perd.

Étant donné l'état du plateau avant que Amy ne fasse son premier coup, sans aucune case rouge adjacente à une case verte, déterminez quelle joueuse gagnera si les deux jouent de manière optimale.

Entrée

L'entrée consiste en plusieurs cas de test. La première ligne contient un entier $T$ ($1 \le T \le 5 \cdot 10^4$) : le nombre de cas de test.

La première ligne de chaque cas de test contient $N$ et $K$ ($1 \le N \le 2 \cdot 10^5$, $0 \le K \le \min(N - 1, 7)$).

La deuxième ligne de chaque cas de test contient une chaîne de $N$ caractères décrivant l'état initial du plateau. Chaque caractère est soit R (rouge), G (vert), ou W (blanc). Il est garanti qu'aucun R n'est adjacent à un G.

Il est garanti que la somme de $N$ sur tous les cas de test n'excède pas $4 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez soit Amy, soit Aimee, indiquant la joueuse qui gagnera.

Scoring

• ($15$ points) $N \le 10$.
• ($15$ points) Aucune paire de cases blanches n'est adjacente dans l'état initial.
• ($10$ points) L'état initial est entièrement blanc, et $K = 0$.
• ($20$ points) $K = 0$.
• ($40$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

5
5 4
WWWWW
16 3
RRRRWGGGGGWRRRRR
6 5
WWWWWW
12 0
WWWWRRWGGGWW
13 7
WRRWWGWRWRWWW

Sortie 1

Amy
Aimee
Aimee
Amy
Amy

Remarque

Dans le premier cas de test, Amy peut gagner en choisissant $S$ comme étant l'ensemble du plateau et en le coloriant entièrement en rouge lors de son premier tour.

Dans le deuxième cas de test, Amy ne peut pas effectuer de coup légal lors de son premier tour, et elle perd immédiatement.

Dans le troisième cas de test, peu importe ce qu'Amy fait lors de son premier coup, Aimee est toujours capable de colorier l'ensemble du plateau avec la même couleur lors de son tour, gagnant ainsi la partie.