약수 집합의 포함

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제 설명

예제1

문제

두 정수 $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를 출력한다.