Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Chef and Divyam are playing a game. They start with a rational number $X$, such that $0 < X < 1$.

In each turn, Chef chooses a positive real number $Y$. Then Divyam either adds or subtracts $Y$ to $X$. So $X$ is replaced with either $X+Y$ or $X-Y$. If this number becomes $0$ or $1$, then Chef wins. Otherwise, the game continues.

You are given $X$, and you have to determine whether Chef can win in a finite number of moves. More formally, does there exist a finite number $N$ so that Chef has a strategy that is guaranteed to win in at most $N$ moves?

Here, $X$ will be given in the form $\frac{A}{B}$, where $A$ and $B$ are positive integers, $A < B$ and $\gcd(A,B)=1$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $A$ and $B$.

------  Output ------
For each test case, print a single line containing the string "Yes" if Chef can win the game in a finite number of moves and "No" otherwise (without quotes). You can print "Yes" or "No" in any case.

------  Constraints ------
$1 ≤ T ≤ 10^{6}$
$1 ≤ A < B ≤ 10^{18}$
$\gcd(A, B)=1$

------  Subtasks ------
Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
2
1 2
2 3
----- Sample Output 1 ------ 
Yes
No
----- explanation 1 ------ 
Test case 1: Chef will choose $Y=\frac{1}{2}$, so whatever Divyam does, the number will become $0$ or $1$. Hence Chef will win in a finite number of moves. 

Test case 2: No matter what Chef chooses, it can be shown that Divyam can make sure Chef never wins.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
l = 1000000000000000001
p = 1
c = {}
while p <= l:
	c[str(p)] = True
	p *= 2
for i in range(t):
	(a, b) = input().split()
	print('Yes' if c.get(b, False) else 'No')


t = int(input())
lim = 1000000000000000001
p = 1
check = {}
while p <= lim:
	check[str(p)] = True
	p = p * 2
for _ in range(t):
	(a, b) = input().split()
	if check.get(b, False):
		print('Yes')
	else:
		print('No')


from math import ceil, floor, log2
import io, os, time, sys
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l2 = log2(b)
	if ceil(l2) == floor(l2):
		print('Yes')
	else:
		print('No')


import sys
t = int(sys.stdin.readline())
for k in range(t):
	(a, b) = map(int, sys.stdin.readline().split())
	if b & b - 1 == 0:
		print('Yes')
	else:
		print('No')


D = {}
x = 1
for i in range(60):
	D[str(x)] = True
	x *= 2
T = int(input())
ans = []
for _ in range(T):
	(A, B) = input().split()
	if B in D:
		ans.append('Yes')
	else:
		ans.append('No')
for i in ans:
	print(i)


import sys
t = int(input())
for i in range(t):
	(a, b) = map(int, sys.stdin.readline().split())
	if b & b - 1:
		print('No')
	else:
		print('Yes')


import math
import sys

def isPowerOfTwo(x):
	return x and (not x & x - 1)
t = int(sys.stdin.readline())
while t > 0:
	(a, b) = map(int, sys.stdin.readline().split())
	if isPowerOfTwo(b):
		print('Yes')
	else:
		print('No')
	t -= 1


import sys
import math
T = int(input())
for _ in range(T):
	(a, b) = map(int, sys.stdin.readline().split())
	log2b = int(math.log2(b))
	if 2 ** log2b == b:
		print('Yes')
	else:
		print('No')


import sys
for _ in range(int(input())):
	(preethi, ash) = map(int, sys.stdin.readline().split())
	while ash % 2 == 0:
		ash = ash / 2
	if ash == 1:
		sys.stdout.write('Yes')
	else:
		sys.stdout.write('No')
	sys.stdout.write('\n')


import sys
T = int(sys.stdin.readline())
ansarr = []
for ntc in range(1, T + 1):
	(A, B) = map(int, sys.stdin.readline().split())
	while B & 1 == 0:
		B >>= 1
	ans = 'Yes\n' if B == 1 else 'No\n'
	sys.stdout.write(ans)


T = int(input())
ansarr = []
for ntc in range(1, T + 1):
	(A, B) = map(int, input().split())
	while B & 1 == 0:
		B >>= 1
	ans = 'Yes' if B == 1 else 'No'
	ansarr.append(ans)
print('\n'.join(ansarr))


import sys
try:
	t = int(input())
	p = 10 ** 9 + 7
	for k in range(t):
		(a, b) = map(int, sys.stdin.readline().split())
		if b & b - 1 == 0:
			print('Yes')
		else:
			print('No')
except:
	pass


from sys import stdin, stdout
for t in range(int(stdin.readline())):
	(a, b) = map(int, stdin.readline().split())
	while b % 2 == 0:
		b /= 2
	if b == 1:
		print('Yes')
	else:
		print('No')


import sys

def ptwo(n):
	if n == 0:
		return False
	while n != 1:
		if n % 2 != 0:
			return False
		n = n // 2
	return True
for _ in range(int(input())):
	(a, b) = map(int, sys.stdin.readline().split())
	if ptwo(b):
		sys.stdout.write('Yes')
	else:
		sys.stdout.write('No')
	sys.stdout.write('\n')


import sys
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def inp():
	return int(input())

def ma():
	return map(int, input().split())
for _ in range(inp()):
	(a, b) = ma()
	if b & b - 1 == 0:
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(a, b) = ma()
	if a % 2 and bin(b)[2:].count('1') == 1:
		print('Yes')
	else:
		print('No')


import sys

def check(n, m):
	for i in range(1, 64):
		if m == 1 << i and n % 2 == 1:
			return True
	return False
t = int(sys.stdin.readline())
for tt in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	print('Yes') if check(n, m) else print('No')


import sys
for _ in range(int(input())):
	(a, b) = map(int, sys.stdin.readline().split())
	while b % 2 == 0:
		b = b // 2
	if b == 1:
		print('Yes')
	else:
		print('No')


import sys
import os.path
import math
import heapq
from sys import stdin, stdout
from collections import *
from math import gcd, ceil, floor
mod = int(1000000000.0 + 7)
if os.path.exists('Updated prg/Input3d.txt'):
	sys.stdout = open('Updated prg/Output3d.txt', 'w')
	sys.stdin = open('Updated prg/Input3d.txt', 'r')

def sinp():
	return input()

def ninp():
	return int(sinp())

def mapinp():
	return map(int, sinp().split())

def smapinp():
	return map(str, sinp().split())

def fastinp():
	return map(int, sys.stdin.readline().split())

def linp():
	return list(mapinp())

def sl():
	return list(sinp())

def prnt(a):
	print(a)

def prntl(a):
	print(a, end=' ')

def prntlist(a):
	print(*a)
for _ in range(ninp()):
	(A, B) = fastinp()
	while B % 2 == 0:
		B = B // 2
	if B == 1:
		print('Yes')
	else:
		prnt('No')


import sys
for _ in range(int(input())):
	(a, b) = sys.stdin.readline().split()
	c = bin(int(b)).replace('0b', '')
	if c.count('1') == 1:
		sys.stdout.write('Yes' + '\n')
	else:
		sys.stdout.write('No' + '\n')


def canWin(A, B):
	n = 1
	val = 1
	while val <= B:
		if val == B:
			return 'Yes'
		else:
			val = 1 << n
			n += 1
	return 'No'
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	(A, B) = map(int, stdin.readline().split())
	print(canWin(A, B))


import sys, os, io
t = int(input())
for _ in range(t):
	(a, b) = map(int, sys.stdin.readline().split())
	if b & b - 1 == 0:
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline
ans = []
power = 2
for _ in range(60):
	ans.append(power)
	power *= 2
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	low = 0
	high = 59
	flag = 0
	while low <= high:
		mid = (low + high) // 2
		if ans[mid] > b:
			high = mid - 1
		elif ans[mid] < b:
			low = mid + 1
		else:
			flag = 1
			break
	if flag == 1:
		print('Yes')
	else:
		print('No')


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def fast_out(n):
	sys.stdout.write(str(n) + '\n')
T = int(input())
for n1 in range(T):
	(a, b) = get_ints()
	while b > 1:
		if b % 2 == 0:
			b = b // 2
		else:
			fast_out('No')
			break
	else:
		fast_out('Yes')


twos = set(['2', '4', '8', '16', '32', '64', '128', '256', '512', '1024', '2048', '4096', '8192', '16384', '32768', '65536', '131072', '262144', '524288', '1048576', '2097152', '4194304', '8388608', '16777216', '33554432', '67108864', '134217728', '268435456', '536870912', '1073741824', '2147483648', '4294967296', '8589934592', '17179869184', '34359738368', '68719476736', '137438953472', '274877906944', '549755813888', '1099511627776', '2199023255552', '4398046511104', '8796093022208', '17592186044416', '35184372088832', '70368744177664', '140737488355328', '281474976710656', '562949953421312', '1125899906842624', '2251799813685248', '4503599627370496', '9007199254740992', '18014398509481984', '36028797018963968', '72057594037927936', '144115188075855872', '288230376151711744', '576460752303423488', '1152921504606846976'])
fives = set(['5', '25', '125', '625', '3125', '15625', '78125', '390625', '1953125', '9765625', '48828125', '244140625', '1220703125', '6103515625', '30517578125', '152587890625', '762939453125', '3814697265625', '19073486328125', '95367431640625', '476837158203125', '2384185791015625', '11920928955078125', '59604644775390625', '298023223876953125', '1490116119384765625'])
for T in range(int(input())):
	(a, b) = input().split()
	if b in twos:
		print('Yes')
	else:
		print('No')


from sys import stdin
try:
	t = int(stdin.readline())
	for i in range(t):
		(a, b) = map(int, stdin.readline().split())
		while b % 2 == 0:
			b /= 2
		if b == 1:
			print('Yes')
		else:
			print('No')
except EOFError as e:
	raise e


from sys import stdin, stdout
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
for _ in range(ip()):
	(a, b) = inp()
	s = bin(b)
	s = s[2:]
	l = 0
	for i in range(len(s)):
		if s[i] == '1':
			l += 1
		if l > 1:
			break
	if l == 1:
		print('Yes')
	else:
		print('No')