Divisor Set Inclusion

You are given two integers $a$ and $b$. Determine whether the set of divisors of $a$ is contained in the set of divisors of $b$.

The first line contains a single integer $z$ ($1 \le z \le 10^6$), the number of data sets. Each of the next $z$ lines describes one data set and contains two integers $a$, $b$ ($1 \le a, b \le 10^9$) separated by a space.

Print $z$ lines. Each line contains the answer for one data set. If the set of divisors of $a$ is contained in the set of divisors of $b$, print TAK; otherwise print NIE.