#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fors(i, l, r, d) for (int i = l; r; i += d)
#define forb(i, l, r, d) for (int i = l; r; i -= d)
const int man = 1e9+10;

int T, n, k;
vector <int> a;
bool dfs (int d, int p, int m) {
//	printf("%d %d %d\n", d, p, m);
	if (!d) return p==1;
	int l = d, u = 1;
	fors(i, m, i<a.size() && l--, 1) {
		if ((u*=a[i]) > p) return 0;
//		u *= a[i];
//		cout << u << endl;
	}
	l = d;
	fors(i, m, i < a.size(), 1) {
		if (i+l-1 > a.size() || u > p) return 0;
		if (i != m+1) u = u/a[i-1]*a[i];
//		printf("K%d %d %d %d\n", u, l, a[i-1], a[i]);
		if (!(p%a[i]) && dfs(d-1, p/a[i], i+1)) return 1;
	} if (!d) return p==1;
	return 0;
}
int main () {
	#ifndef ONLINE_JUDGE
		freopen("test.in", "r", stdin);
		freopen("test.out", "w", stdout);
	#endif
	scanf("%d", &T);
	while (T --) {
		a.clear();
		scanf("%d%d", &n, &k);
		if (k >= 13) {
			puts("NIE");
			continue;
		} fors(i, 1, i <= ceil(sqrt(n)), 1) 
			if (!(n%i)) {
				a.push_back(i);
				if (i*i != n) a.push_back(n/i);
			}
		sort(a.begin(), a.end());
		if (dfs(k, n, 0)) puts("TAK");
		else puts("NIE");
	} return 0;
}

就是在泥古测评姬上RE，本地没问题