Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Sebi likes solving Rubik's cube a lot. He spends a lot of time in getting expertize in solving not only the 3 * 3 * 3 cube, but also the cubes of higher dimensions like 4 * 4 * 4, 5 * 5 * 5 and so on.

Chefland has a very famous toy shop which sells Rubik's cubes. This shop has interesting rules. Each day it sells cubes of a fixed dimension. Sebi has to buy new cubes daily primarily due to two reasons, one he handles the cube very roughly and the other that he solves the cube so many times during the day.

Today the shop is selling K * K * K size Rubik's cubes. In the morning, Sebi bought a cube from the shop. He had just started playing with it, suddenly his cute little sisters asked him to give them C units of the cube. Sebi's did not want to disappoint his sisters, so he immediately disassembled the cube into K * K * K units and gave C of those to his sisters.

Now Sebi wants to solve the Rubik's cube again, so he thought of going to market and buy some cubes so that he can create a Rubik's cube from those. The newly created cube can be of any dimension. For achieving that, he can disassemble and reassemble the cubes in the way he wants, but he does not want to waste any units of the cubes.

Can you please tell whether Sebi will be able to build such a Rubik's cube or not?

------ Input ------ 

The first line of the input contains an integer T denoting the number of the test cases.
Each test case contains two space separated integers K, C as defined in the statement.

------ Output ------ 

For each test case, output a single line containing "YES" or "NO" (without quotes) corresponding to the situation.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$0 ≤ C ≤ K^{3}$
$2 ≤ K  ≤ 100$

----- Sample Input 1 ------ 
2
2 5
2 2
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
Example case 1. In this case Sebi bought a Rubik's of size 2 * 2 * 2. His sisters wanted 5 units of cube. He disassembled the cube into 8 units immediately and gave 5 of them to his sisters. Now he is left with 3 units. He buys 3 cubes at the shop. Now, after disassembling, he has 3 + 3 * 8 = 27 cubes. By making use of these 27 cubes, he can make a Rubik's cube of size 3 * 3 * 3.

Difficulty: VERY_HARD
Tags: Number theory

Preprocessing

Mathematics

Starter code:

Solutions:
from collections import Counter
if 1 == 1:
	if 1 == 1:
		n = 100
		smallest = [1 for i in range(n + 1)]
		for i in range(2, n + 1):
			if smallest[i] == 1:
				smallest[i] = 0
				for j in range(2, n // i + 1):
					if smallest[i * j] == 1:
						smallest[i * j] = i
		prime = []
		position = {}
		for k in range(2, len(smallest)):
			if smallest[k] == 0:
				position[k] = len(prime)
				prime += [k]
		for x in prime:
			smallest[x] = x

		def listfactor(R):
			T = []
			while R > 1:
				temp = smallest[R]
				T += [temp]
				R = R // temp
			return Counter(T)
result = [[] for i in range(len(prime))]
small = set([2, 3, 5, 7])
for i in range(len(result)):
	if prime[i] not in small:
		a = prime[i] ** 3
		temp = [0] * a
		for j in range(a):
			temp[j ** 3 % a] = 1
		result[i] += [temp]
	elif prime[i] == 2:
		for j in range(1, 7):
			a = (prime[i] ** j) ** 3
			temp = [0] * a
			for k in range(a):
				temp[pow(k, 3, a)] = 1
			result[i] += [temp]
	elif prime[i] == 3:
		for j in range(1, 5):
			a = prime[i] ** (3 * j)
			temp = [0] * a
			for k in range(a):
				temp[pow(k, 3, a)] = 1
			result[i] += [temp]
	else:
		for j in range(1, 3):
			a = prime[i] ** (3 * j)
			temp = [0] * a
			for k in range(a):
				temp[pow(k, 3, a)] = 1
			result[i] += [temp]
T = int(input())
for _ in range(T):
	(K, C) = list(map(int, input().strip().split(' ')))
	P = listfactor(K)
	a = K ** 3 - C
	check = 0
	for p in P:
		r = P[p]
		r = r - 1
		t = position[p]
		TTT = result[t][r]
		need = a % p ** (3 * r + 3)
		if TTT[need] == 0:
			check = 1
			break
	if check == 0:
		print('YES')
	else:
		print('NO')