Madoka is going to enroll in "TSUNS PTU". But she stumbled upon a difficult task during the entrance computer science exam:

A number is called good if it is a multiple of $d$.

A number is called beatiful if it is good and it cannot be represented as a product of two good numbers.

Notice that a beautiful number must be good.

Given a good number $x$, determine whether it can be represented in at least two different ways as a product of several (possibly, one) beautiful numbers. Two ways are different if the sets of numbers used are different.

Solve this problem for Madoka and help her to enroll in the best school in Russia!


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — number of test cases. Below comes their description.

Each test case consists of two integers $x$ and $d$, separated by a space ($2 \leq x, d \leq 10^9$). It is guaranteed that $x$ is a multiple of $d$.


-----Output-----

For each set of input data, output "NO" if the number cannot be represented in at least two ways. Otherwise, output "YES".

You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).


-----Examples-----

Input
8
6 2
12 2
36 2
8 2
1000 10
2376 6
128 4
16384 4
Output
NO
NO
YES
NO
YES
YES
NO
YES


-----Note-----

In the first example, $6$ can be represented as $6$, $1 \cdot 6$, $2 \cdot 3$. But $3$ and $1$ are not a good numbers because they are not divisible by $2$, so there is only one way.

In the second example, $12$ can be represented as $6 \cdot 2$, $12$, $3 \cdot 4$, or $3 \cdot 2 \cdot 2$. The first option is suitable. The second is— no, because $12$ is not beautiful number ($12 = 6 \cdot 2$). The third and fourth are also not suitable, because $3$ is not good number.

In the third example, $36$ can be represented as $18 \cdot 2$ and $6 \cdot 6$. Therefore it can be decomposed in at least two ways.

Difficulty: HARD
Tags: Number theory

Dynamic programming

Mathematics

Constructive algorithms
Skill types: Dynamic programming

Starter code:

Solutions:
from math import sqrt

def primeCheck(n):
	t = 0
	if n == 1:
		return True
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				t = 1
				break
		if t == 0:
			return True
		else:
			return False
	else:
		return False
T = int(input())
for t in range(T):
	(x, d) = map(int, input().split())
	cout = 0
	while x > 0 and x % d == 0:
		cout += 1
		x //= d
	if cout > 1 and (not primeCheck(x)):
		print('YES')
	elif cout > 2 and (not primeCheck(d)):
		res = False
		i = 2
		while i <= int(sqrt(d)):
			if d % i == 0:
				if x * i % d:
					res = True
					break
				else:
					if x * i % d:
						res = True
						break
					if x * (d // i) % d:
						res = True
						break
			i += 1
		if res or cout > 3:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


from sys import stdin
import math
from collections import deque
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
input = stdin.readline

def ceil(m, n):
	val = m // n
	if m % n != 0:
		return val + 1
	return val

def isprime(v):
	if v == 1:
		return True
	for i in range(2, int(math.sqrt(v)) + 1):
		if v % i == 0:
			return False
	return True
for _ in range(int(input())):
	(x, d) = map(int, input().split())
	(temp, times) = (x, 0)
	while temp % d == 0:
		times += 1
		temp //= d
	if times <= 1:
		print('NO')
		continue
	if times == 2:
		if not isprime(temp):
			print('YES')
		else:
			print('NO')
		continue
	if not isprime(temp):
		print('YES')
	elif isprime(d):
		print('NO')
	elif d == temp ** 2 and times == 3:
		print('NO')
	else:
		print('YES')


def isPrime(n):
	if n == 1:
		return True
	if n < 2:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def factor(n):
	ans = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			ans.append(i)
			ans.append(n // i)
	return ans
for lkdl in range(int(input())):
	(x, d) = map(int, input().split())
	c = 0
	while x % d == 0:
		x = x // d
		c += 1
	if c == 1:
		print('NO')
	elif isPrime(x):
		if isPrime(d):
			print('NO')
		elif c == 2:
			print('NO')
		elif c >= 4:
			print('YES')
		else:
			f = factor(d)
			ans = 'NO'
			for i in f:
				if i * d * x % (d * d) != 0:
					ans = 'YES'
					break
			print(ans)
	else:
		print('YES')


import sys
from math import sqrt, gcd, factorial
from collections import deque, Counter, OrderedDict
sys.setrecursionlimit(10 ** 6)
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007

def isPrime(n):
	flag = 0
	if n == 1:
		return True
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				flag = 1
				break
		if flag == 0:
			return True
		else:
			return False
	else:
		return False

def solver(n):
	global ans
	i = 2
	while i <= int(sqrt(n)):
		if n % i == 0:
			if x * i % d:
				ans = True
				break
			else:
				if x * i % d:
					ans = True
					break
				if x * (n // i) % d:
					ans = True
					break
		i += 1
for _ in range(I()):
	(x, d) = M()
	c = 0
	while x > 0 and x % d == 0:
		c += 1
		x //= d
	if c > 1 and (not isPrime(x)):
		print('YES')
	elif c > 2 and (not isPrime(d)):
		ans = False
		solver(d)
		if ans or c > 3:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


import math

def isprime(n):
	sq = int(math.sqrt(n))
	i = 2
	while i <= sq:
		if n % i == 0:
			return False
		i += 1
	return True

def check(x):
	cnt = 1
	while x % d == 0:
		cnt += 1
		x /= d
	return cnt <= 2
T = int(input())
for _ in range(T):
	(x, d) = list(map(int, input().split()))
	(p, tmp) = (0, x)
	while tmp % d == 0:
		p += 1
		tmp /= d
	if p <= 1:
		print('NO')
		continue
	if not isprime(d):
		if p >= 4:
			print('YES')
			continue
	(cnt, val) = (0, -1)
	i = 2
	while i * i <= tmp:
		while tmp % i == 0:
			cnt += 1
			val = i
			tmp /= i
		i += 1
	if tmp != 1:
		val = tmp
		cnt += 1
	if cnt >= 2:
		print('YES')
		continue
	if isprime(d):
		print('NO')
		continue
	if p == 2:
		print('NO')
		continue
	if cnt == 0:
		print('YES')
		continue
	fk = 0
	for i in range(2, d):
		if d % i == 0:
			(v1, v2) = (d * val * i, d * (d / i))
			if check(v1) and check(v2):
				print('YES')
				fk = 1
				break
			(v1, v2) = (d * val * (d / i), d * i)
			if check(v1) and check(v2):
				print('YES')
				fk = 1
				break
	if fk == 0:
		print('NO')


def prime(n):
	if n % 2 == 0 and n != 2:
		return False
	for i in range(3, int(n ** 0.5 + 1), 2):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	(x, d) = map(int, input().split())
	ans = 0
	while x % d == 0:
		ans += 1
		x //= d
	if ans == 1:
		print('NO')
	elif ans == 2:
		if prime(x):
			print('NO')
		else:
			print('YES')
	elif prime(x) and prime(d):
		print('NO')
	elif prime(x) and ans == 3 and (d == x ** 2):
		print('NO')
	else:
		print('YES')


import math

def primFrac(n):
	num = 2
	primFac = []
	while num * num <= n:
		while n % num == 0:
			primFac.append(num)
			n = n / num
		num = num + 1
	if n > 1:
		primFac.append(n)
	return primFac

def first(x, d):
	counter = 0
	while x % d == 0:
		x /= d
		counter += 1
	return (counter, int(x))

def is_prime(n):
	if n == 1:
		return True
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def answer(x, d, list, counter1, counter, d_list, d_len, new_x):
	if counter == 1:
		print('NO')
	elif not is_prime(new_x):
		print('YES')
	elif counter < 3:
		print('NO')
	elif is_prime(d):
		print('NO')
	elif counter == 3 and d % new_x == 0 and (int(d / new_x) == new_x):
		print('NO')
	else:
		print('YES')
number = int(input())
for i in range(number):
	(x, d) = input().split()
	(x, d) = (int(x), int(d))
	(counter, new_x) = first(x, d)
	list = primFrac(new_x)
	counter1 = len(list)
	d_list = primFrac(d)
	d_len = len(d_list)
	answer(x, d, list, counter1, counter, d_list, d_len, new_x)


from math import sqrt

def prime(a):
	for i in range(2, int(sqrt(a)) + 1):
		if a % i == 0:
			return False
	return True
for _ in range(int(input())):
	(x, d) = map(int, input().strip().split())
	co = True
	n = 1
	for i in range(2, 31):
		if x % d ** i == 0:
			n = i
		elif d ** i > x:
			break
	p = x // d ** min(n, 2)
	q = x // d ** n
	if n == 1:
		co = False
	elif n == 2:
		if prime(p):
			co = False
	elif n == 3:
		if prime(q) == False:
			co = True
		elif prime(d):
			co = False
		elif sqrt(d) == q and prime(sqrt(d)):
			co = False
	elif prime(q) == False:
		co = True
	elif prime(d):
		co = False
	if co:
		print('YES')
	else:
		print('NO')


def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return i
	return -1

def is_Power(x, y):
	while x % y == 0:
		x = x / y
	return x == 1
t = int(input())

def isBeautiful(n, x):
	return n % x == 0 and n % x ** 2 != 0
for i in range(t):
	(x, d) = input().split(' ')
	x = int(x)
	d = int(d)
	count = 0
	while x % d == 0:
		count += 1
		x //= d
	if count < 2:
		print('NO')
	else:
		if isPrime(x) != -1:
			print('YES')
			continue
		if isPrime(d) != -1 and isPrime(d) * isPrime(d) == d:
			if x == isPrime(d) and count == 3:
				print('NO')
				continue
		if count > 2 and isPrime(d) != -1:
			print('YES')
			continue
		print('NO')