AlgoLiga 2018

Jaś i Małgosia, pozostawieni przez rodziców w lesie, po trzydniowej tułaczce dotarli do przepięknej chatki zbudowanej z różnych smakołyków. Głodne rodzeństwo postanowiło zjeść domek. Niestety nasi bohaterowie zaczęli kłócić się o to, które z nich skonsumuje najsmaczniejsze kawałki. Ponieważ nie mogli dojść do porozumienia, postanowili zagrać w grę, której zwycięzca je wszystko na co tylko ma ochotę. Zasady gry są następujące:

• Na stoliku stoi rządek n babek.
• Jaś i Małgosia wykonują ruchy na przemian.
• W każdym ruchu gracz musi zabrać z rządku dokładnie k sąsiadujących ze sobą babek.
• Grę przegrywa ten gracz, który nie może wykonać ruchu.
• Pierwszy ruch wykonuje Małgosia

Odpowiedz na pytanie, które z dzieci wygra grę przy założeniu, że obydwoje grają optymalnie?

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;1275] określająca liczbę zestawów danych. W kolejnych t liniach znajdują się zestawy danych. Każdy zestaw składa się z dwóch liczb całkowitych n ∈ [1;50] i k ∈ [1;n] opisanych w treści zadania.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać literę M jeżeli grę wygra Małgosia albo J w przeciwnym wypadku.

Przykład

Wejście

2
5 2
5 3

Wyjście

J
M

Wyjaśnienie do przykładu

W pierwszym przypadku Małgosia po swoim ruchu pozostawi na stole 3 babki, a zatem niezależnie od ich ustawienia musi przegrać gdyż Jaś zabierze 2 z nich.

W drugim teście już po pierwszym ruchu pozostaną 2 babki zamiast wymaganych 3 i tutaj Małgosia wygrywa.