Problem description

Back
Show PDF
Skoki
(I)
Limit pamięci: 512 MB
Limit czasu: 1.00 s

Poruszamy się po okręgu z polami ponumerowanymi od 0 do n − 1. Zaczynamy w polu 0, a następnie wykonujemy dowolną sekwencję skoków o długości k1 lub k2 zgodnie z ruchem wskazówek zegara.

Chcemy sprawdzić, czy możliwe jest odwiedzenie wszystkich pól okręgu (czyli z pola 0 da się w kolejnych krokach wejść przynajmniej raz do każdego pola).

Mamy dowolną liczbę kroków oraz możemy odwiedzać poszczególne pola wielokrotnie.

Wejście

W pierwszej linii wejścia znajduje się liczba całkowita q — liczba zapytań. Każde z kolejnych q wierszy zawiera trzy liczby całkowite n, k1 oraz k2.

Wyjście

Dla każdego zapytania wypisz w osobnej linii słowo TAK, jeśli da się odwiedzić wszystkie pola, lub NIE w przeciwnym wypadku.

Uwaga: słowa TAK i NIE muszą być zapisane wielkimi literami.

Ograniczenia

  • 1 ≤ q ≤ 1 000
  • 1 ≤ n ≤ 109
  • 1 ≤ k1, k2 ≤ n − 1

Przykład

Wejście Wyjście Wyjaśnienie 
3
6 2 3
7 2 4
6 2 4

TAK
TAK
NIE

Dla n = 6, k1 = 2, k2 = 3: przykładowa sekwencja skoków umożliwiająca odwiedzenie wszystkich pól to:
$$ 0 \xrightarrow{+2} 2 \xrightarrow{+2} 4 \xrightarrow{+3} 1 \xrightarrow{+2} 3 \xrightarrow{+2} 5 $$

Dla n = 7, k1 = 2, k2 = 4: wystarczy wykonywać skok  + 2 sześć razy:
$$ 0 \xrightarrow{+2} 2 \xrightarrow{+2} 4 \xrightarrow{+2} 6 \xrightarrow{+2} 1 \xrightarrow{+2} 3 \xrightarrow{+2} 5 $$

Dla n = 6, k1 = 2, k2 = 4: da się udowodnić, że nie ma możliwości odwiedzenia wszystkich pól.