약수 집합의 포함

시간 제한1초메모리 제한128 MB

요약

a의 모든 약수가 b의 약수인지, 즉 a가 b를 나누는지 각 쌍마다 판정합니다.

난이도: 쉬움10점 중 3점
유형: 정수론
정답자: 아직 제출이 없습니다

문제

두 정수 $a$ 와 $b$ 가 주어진다. $a$ 의 약수들의 집합이 $b$ 의 약수들의 집합에 포함되는지 판별하여라.

입력

첫째 줄에 데이터 집합의 개수를 나타내는 정수 $z$ ( $1 \le z \le 10^6$ )가 주어진다. 이어지는 $z$ 개의 줄에는 각 데이터 집합의 정보가 주어진다. 각 줄에는 두 정수 $a$ , $b$ ( $1 \le a, b \le 10^9$ )가 공백으로 구분되어 주어진다.

출력

$z$ 개의 줄을 출력한다. 각 줄에는 하나의 데이터 집합에 대한 답을 출력한다. $a$ 의 약수 집합이 $b$ 의 약수 집합에 포함되면 TAK을, 그렇지 않으면 NIE를 출력한다.

예제1

예제 1
입력
```
3
2 3
2 4
4 10
```
예상 출력
```
NIE
TAK
NIE
```