POLSKI SPOJ

Przed rozwiązaniem tego poziomu zaleca się przejście poprzedniego : Cwany Lutek

Na tym etapie Lutek i jego m tygrysów mają niesłychaną zagadkę dla ciebie.
Jak się domyślasz tygrysy nie są normalne. Ich ulubionym przysmakiem są żelocuxy, ale to nie to jest w nich najdziwniejsze. Ich formą odżywiania jest... wdychanie oparów żelocuxów.
Mając n żelocuxów oraz n różnych zbiorników oraz n inhalatorów dla tygrysów, w każdym zbiorniku po jednym żelocuxie, Lutek chciałby odprowadzić jak największą liczbę mieszanek żelocuxów do inhalatorów.

Każda mieszanka jest scharakteryzowana jako k pomieszanych z sobą oparów z żelocuxów.

Dla przykładu mając 3 żelocuxy, 3 tygrysy oraz liczbę k równą 2 możemy odprowadzić jedną mieszankę pierwszemu tygrysowi z 1 zbiornika oraz drugiego zbiornika. Daną mieszankę możemy oznaczyć jako [1,2].

Dla drugiego tygrysa możemy odprowadzić mieszankę [2,3]
Natomiast dla ostatniego tygrysa możemy odprowadzić mieszankę [1,3].

Wbrew zaleceniom jest, aby dwa różne tygrysy otrzymywały taką samą mieszankę oparów.

Pomóż Lutkowi stwierdzić czy dla danego n,k,m można tak przydzielić wszystkie możliwe mieszanki tygrysom, aby każdy z nich dostał taką samą ilość.

Input

W pierwszej linii liczba t<=1000, liczba testów.

W następnych t liniach liczby n,k,m oznaczające kolejno : liczbę żelocuxów( w tym także inhalatorów oraz zbiorników), zalecana ilość zmieszanych oparów, liczba tygrysów. k jest tak dobrane, aby zawsze było liczbą pierwszą. Podobno wtedy tygrysy bardzo to lubią.

0<n,k,m<=10^9

Output

Dla każdego testu w osobnej linii TAK jeżeli można rozdzielić mieszanki według zaleceń opisanych wcześniej. W przeciwnym wypadku należy wypisać NIE

Example

Input:
1
3 2 3
Output:
TAK