#include <iostream>
#include <cmath>
using namespace std;
 
bool is_concluded(int x, int y) {
	for (int i = 2; i * i <= x; ++i) {
		if (x % i == 0) {
			if (y % i != 0) return false;
			while (x % i == 0) x /= i;
		}
	}
	if (x > 1) {
		if (y % x != 0) return false;
	}
	return true;
}
 
int main() {
	int n;
	cin >> n;
	while (n--) {
		int a, b;
		cin >> a >> b;
		if (is_concluded(a, b))
			cout << "TAK" << endl;
		else
			cout << "NIE" << endl;
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpib29sIGlzX2NvbmNsdWRlZChpbnQgeCwgaW50IHkpIHsKCWZvciAoaW50IGkgPSAyOyBpICogaSA8PSB4OyArK2kpIHsKCQlpZiAoeCAlIGkgPT0gMCkgewoJCQlpZiAoeSAlIGkgIT0gMCkgcmV0dXJuIGZhbHNlOwoJCQl3aGlsZSAoeCAlIGkgPT0gMCkgeCAvPSBpOwoJCX0KCX0KCWlmICh4ID4gMSkgewoJCWlmICh5ICUgeCAhPSAwKSByZXR1cm4gZmFsc2U7Cgl9CglyZXR1cm4gdHJ1ZTsKfQoKaW50IG1haW4oKSB7CglpbnQgbjsKCWNpbiA+PiBuOwoJd2hpbGUgKG4tLSkgewoJCWludCBhLCBiOwoJCWNpbiA+PiBhID4+IGI7CgkJaWYgKGlzX2NvbmNsdWRlZChhLCBiKSkKCQkJY291dCA8PCAiVEFLIiA8PCBlbmRsOwoJCWVsc2UKCQkJY291dCA8PCAiTklFIiA8PCBlbmRsOwoJfQoJcmV0dXJuIDA7Cn0=

Mwo0IDEwCjggNAo3IDc=

3
4 10
8 4
7 7