Mamy dane dwie liczby całkowite a i b. Należy sprawdzić, czy zbiór dzielników liczby a, zawiera się w zbiorze dzielników liczby b.

입력 형식

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą z (1 ≤ z ≤ 10⁶), oznaczającą liczbę zestawów danych. W n kolejnych wierszach znajdują się opisy kolejnych zestawów. Każdy wiersz zawiera dwie liczby całkowite a, b (1 ≤ a, b ≤ 10⁹), oznaczające liczby z treści zadania.

출력 형식

Standardowe wyjście powinno zawierać n wierszy. W każdym wierszu odpowiedź na zapytanie dla jednego zestawu danych. Jeśli zbiór dzielników liczby a należy do zbioru dzielników liczby b, to należy wypisać jedno słowo 'TAK', w przeciwnym wypadku jedno słowo 'NIE'.

예제 입력

3
2 3
2 4
4 10

예제 출력

NIE
TAK
NIE