Divisor Set Inclusion

Time limit1sMemory limit128 MB

Summary

Decide for each pair whether every divisor of a also divides b, which holds exactly when a divides b.

Level: Easy3 of 10
Topics: Number theory
Solved: No attempts yet

Problem

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$ .

Input

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.

Output

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.

Examples1

Example 1
Input
```
3
2 3
2 4
4 10
```
Expected output
```
NIE
TAK
NIE
```