A and B are brothers and like playing with marbles.Their mother buys them N marbles to play with.The preciousness of each marble is a natural number from 1 to N and no two marbles have same preciousness.
Since A and B are good at maths they want to divide all those N marbles among them in such a way that sum of the preciousness of all marbles that A receives and sum of the preciousness of all marbles that B receives after distribution are co-primes i.e the gcd(greatest common divisor) of their sum is 1.
Also the absolute value of difference between the sum of the preciousness of marbles of A and B should be exactly M.
Help A and B in finding whether such a distribution of N marbles between them is possible or not.

Formally, you have to tell whether you can distribute first N natural numbers in two sets such that the absolute difference of the sum of numbers in the two sets is equal to M and the gcd of their sum is 1.

Note that one of the set can be empty and greatest common divisor of 0 and k is k

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N  and M denoting the number of marbles and the absolute difference of sum respectively. 
 
------ Output ------ 

For each test case, output a single line.

Print “Yes” if there exist a valid distribution of marbles between A and B else print “No”.

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

$1 ≤ T ≤ 20$
$1 ≤ N ≤ 1,000,000,000$

$0 ≤ M ≤ 10^{18}$

----- Sample Input 1 ------ 
2
5 7
1 2
----- Sample Output 1 ------ 
Yes
No

Difficulty: MEDIUM
Tags: Mathematics

Ad-hoc

Starter code:

Solutions:
from math import gcd
for _ in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	sum1 = x * (x + 1) // 2
	a = (sum1 + y) // 2
	b = sum1 - a
	if abs(a - b) == y:
		if gcd(a, b) == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


import os, sys, io, math
from array import *
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, m) = map(int, input().split())
	s = n * (n + 1) // 2
	p = (s + m) // 2
	print('Yes' if n == 1 and m == 1 or (2 * p - s == m and gcd(p, s - p) == 1) else 'No')


def gcd(X, Y):
	while Y:
		(X, Y) = (Y, X % Y)
	return abs(X)

def isCoprime(X, Y):
	if gcd(X, Y) == 1:
		return True
	return False
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	temp = N * (N + 1) // 2
	if M >= temp:
		print('No')
	elif (temp - M) % 2 == 1:
		print('No')
	elif isCoprime((temp - M) // 2, (temp - M) // 2 + M):
		print('Yes')
	else:
		print('No')


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	total = n * (n + 1) // 2
	ans = 'No'
	if total > m:
		remain = total - m
		half = remain // 2
		if remain & 1:
			ans = 'No'
		elif math.gcd(half + m, half) == 1:
			ans = 'Yes'
	print(ans)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	total = n * (n + 1) // 2
	a = total + m
	if total <= m:
		print('No')
	elif a % 2 != 0:
		print('No')
	else:
		a = a // 2
		b = total - a
		if math.gcd(a, b) == 1:
			print('Yes')
		else:
			print('No')


import math
tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	total = n * (n + 1) // 2
	ans = 'No'
	if total > m:
		remaining = total - m
		half = remaining // 2
		if not remaining & 1 and math.gcd(half + m, half) == 1:
			ans = 'Yes'
	print(ans)


import math
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	a = N * (N + 1) // 2
	b = (a + M) // 2
	c = a - b
	if b - c == M:
		if math.gcd(b, c) == 1.0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	totalsum = n * (n + 1) // 2
	p = (totalsum + m) // 2
	q = totalsum - p
	if abs(p - q) == m:
		if math.gcd(int(p), int(q)) == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


import math
testCases = int(input())
for testCase in range(testCases):
	(n, m) = map(int, input().split())
	ts = n * (n + 1) // 2
	s2 = (ts + m) // 2
	s1 = ts - s2
	if abs(s2 - s1) == m:
		if math.gcd(s1, s2) == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


import math
t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	sm = n * (n + 1) // 2
	x = (sm + m) // 2
	y = sm - x
	if x - y == m:
		if math.gcd(x, y) == 1.0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


from math import gcd
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	tot = n * (n + 1) // 2
	a = (tot + m) // 2
	b = tot - a
	if a - b == m:
		if gcd(a, b) == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


import math
t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	s = n * (n + 1) // 2
	if s < m:
		print('No')
	else:
		x = (s + m) // 2
		y = s - x
		if x + y == s and x - y == m:
			ans = math.gcd(x, y)
			if ans == 1:
				print('Yes')
			else:
				print('No')
		else:
			print('No')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for x1 in range(int(input())):
	x = list(map(int, input().split()))
	su = x[0] * (x[0] + 1) // 2
	if (su - x[1]) % 2 == 1 or x[1] >= su:
		print('No')
		continue
	d = (su - x[1]) // 2
	a = su - d
	val = gcd(a, d)
	if val != 1:
		print('No')
		continue
	print('Yes')


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	sum = n * (n + 1) // 2
	sum2 = (sum - m) // 2
	if (sum + m) % 2 == 1 or sum2 < 0:
		print('No')
		continue
	sum3 = (sum + m) // 2
	num = math.gcd(sum3, sum2)
	if num == 1:
		print('Yes')
	else:
		print('No')


from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	sm = n * (n + 1) // 2
	a = sm + m
	if a & 1:
		print('No')
		continue
	a //= 2
	b = sm - a
	if gcd(a, b) == 1:
		print('Yes')
	else:
		print('No')


import math
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	v = n * (n + 1) // 2
	if m > v:
		print('No')
		continue
	if v & 1:
		if m % 2 == 0:
			print('No')
			continue
	if v % 2 == 0:
		if m & 1:
			print('No')
			continue
	ans1 = (v + m) // 2
	if math.gcd(ans1, abs(v - ans1)) == 1:
		print('Yes')
	else:
		print('No')


from fractions import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = n * (n + 1) // 2
	x = (m + s) // 2
	y = s - x
	if gcd(x, y) == 1 and abs(x - y) == m:
		print('Yes')
	else:
		print('No')


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	res = n * (n + 1) // 2
	a = (res + m) // 2
	b = res - a
	if (m + res) % 2 != 0:
		print('No')
	elif gcd(a, b) == 1:
		print('Yes')
	else:
		print('No')


from fractions import gcd
t = int(input(''))
for i in range(t):
	str = input()
	a = str.split(' ')
	n = int(a[0])
	m = int(a[1])
	s = n * (n + 1) // 2
	x = (s + m) // 2
	y = x - m
	z = gcd(int(x), int(y))
	if s < m:
		print('No')
	elif x + y == s and x - y == m:
		if z == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


from math import gcd as bltin_gcd
t = int(input())
while t:
	try:
		t = t - 1
		str = input()
		a = str.split(' ')
		n = int(a[0])
		m = int(a[1])
		ans = n + 1
		ans = ans * n
		ans = ans // 2
		s1 = (ans + m) // 2
		s2 = s1 - m
		if ans < m:
			print('No')
		elif s1 + s2 == ans and s1 - s2 == m:
			if bltin_gcd(s1, s2) == 1:
				print('Yes')
			else:
				print('No')
		else:
			print('No')
	except EOFError:
		break


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def solve(n, m):
	sumi = n * (n + 1) // 2
	a = (m + sumi) // 2
	b = sumi - a
	if (m + sumi) % 2 != 0:
		print('No')
	elif gcd(a, b) == 1:
		print('Yes')
	else:
		print('No')
t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split(' '))
	solve(n, m)


import math
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	a = int(n * (n + 1) // 2)
	s1 = int((a + m) // 2)
	s2 = abs(m - s1)
	p = int(math.gcd(s1, s2))
	if (m + a) % 2 != 0:
		print('No')
	elif p == 1:
		print('Yes')
	else:
		print('No')


def gcd(elem1, elem2):
	while elem2:
		(elem1, elem2) = (elem2, elem1 % elem2)
	return elem1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	summ = n * (n + 1) // 2
	add = summ + m
	if add % 2 == 0:
		elem1 = add // 2
		elem2 = summ - elem1
		f = gcd(elem1, elem2)
		if f == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = int(n * (n + 1)) // 2
	p = k + m
	if p % 2 != 0:
		print('No')
	else:
		p = int(p // 2)
		x = k - p
		if int(math.gcd(p, x)) == 1:
			print('Yes')
		else:
			print('No')


from fractions import gcd
tc = int(input())
for i in range(tc):
	(summ, flag, arr) = (0, 0, [-1, -1])
	(n, m) = map(int, input().split())
	summ = n * (n + 1) // 2
	if (summ + m) % 2 != 0:
		print('No')
	else:
		(x, y) = ((summ + m) // 2, (summ - m) // 2)
		if gcd(x, y) == 1:
			print('Yes')
		else:
			print('No')


from math import ceil
from math import gcd
t = int(input())
while t > 0:
	string = input().split()
	n = int(string[0])
	m = int(string[1])
	summation = n * (n + 1) // 2
	first = (summation + m) / 2
	second = summation - first
	if (summation + m) % 2 == 0 and gcd((summation + m) // 2, (summation + m) // 2 - m) == 1:
		print('Yes')
	else:
		print('No')
	t -= 1


import math

def coprime2(a, b):
	return math.gcd(a, b) == 1
for i in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	if m == 0:
		print('No')
	else:
		su = n * (n + 1) // 2
		if su < m or (su + m) % 2 != 0:
			print('No')
		else:
			s1 = (su + m) // 2
			s2 = su - s1
			bVal = coprime2(s1, s2)
			if bVal and math.fabs(s1 - s2) == m and (s1 + s2 == su):
				print('Yes')
			else:
				print('No')


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def coprime2(a, b):
	return gcd(a, b) == 1
for i in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	su = int(n * (n + 1) // 2)
	if (su + m) % 2 != 0:
		print('No')
	else:
		s1 = (su + m) // 2
		s2 = su - s1
		bVal = coprime2(s1, s2)
		if bVal:
			print('Yes')
		else:
			print('No')


def GCD(x, y):
	if x == 0:
		return y
	return GCD(y % x, x)

def findAns(summ, m):
	a = (summ + m) // 2
	b = summ - a
	if (summ + m) % 2 != 0:
		print('No')
	elif GCD(a, b) == 1:
		print('Yes')
	else:
		print('No')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	summ = n * (n + 1) // 2
	if summ <= m:
		print('No')
	else:
		findAns(summ, m)


from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = n * (n + 1) // 2
	if (m + s) % 2 != 0:
		print('No')
	else:
		N = (m + s) // 2
		if gcd(N, N - m) == 1:
			print('Yes')
		else:
			print('No')


import math

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
for _ in range(ii()):
	(n, m) = mi()
	x = n * (n + 1) // 2
	y = (x + m) // 2
	if (x + m) % 2 == 0 and math.gcd(y, y - m) == 1:
		print('Yes')
	else:
		print('No')


import math
t = int(input())
for i in range(t):
	t = 'Yes'
	(a, b) = map(int, input().split())
	c = a * (a + 1) // 2 - b
	if c <= 0 or c % 2 != 0:
		t = 'No'
	else:
		d = math.gcd(c // 2 + b, c // 2)
		if d != 1:
			t = 'No'
	print(t)


def hcfnaive(a, b):
	if b == 0:
		return a
	else:
		return hcfnaive(b, a % b)
T = int(input())
for i in range(T):
	(n, m) = [int(x) for x in input().split()]
	sum = n * (n + 1) // 2
	a = (sum + m) // 2
	b = (sum - m) // 2
	if sum % 2 == 1:
		if m % 2 == 1 and m > 0 and (m <= sum - 2):
			if hcfnaive(a, b) == 1:
				print('Yes')
			else:
				print('No')
		else:
			print('No')
	elif sum % 2 == 0:
		if m % 2 == 0 and m > 0 and (m <= sum - 2):
			if hcfnaive(a, b) == 1:
				print('Yes')
			else:
				print('No')
		else:
			print('No')


from math import gcd

def f(N, M):
	S = N * (N + 1) >> 1
	X = S + M >> 1
	return (X, S - X)

def ans(N, M):
	(x, y) = f(N, M)
	if x > 0 and y > 0:
		if abs(x - y) == M and gcd(x, y) == 1:
			return 'Yes'
	return 'No'
T = int(input())
for _ in range(T):
	print(ans(*map(int, input().split())))


from math import gcd as bltin_gcd
t = int(input())
for i in range(t):
	(n, y) = (int(x) for x in input().split())
	sum = n * (n + 1) // 2
	if sum < y:
		print('No')
		continue
	if sum == y:
		print('No')
		continue
	else:
		if (sum + y) % 2 != 0:
			print('No')
			continue
		n1 = (sum + y) // 2
		n2 = sum - n1
		gcd = bltin_gcd(n1, n2)
		if gcd == 1:
			print('Yes')
		else:
			print('No')


from math import gcd
for i in range(int(input())):
	(N, M) = map(int, input().strip().split())
	sumN = N * (N + 1) // 2
	if sumN < M:
		print('No')
	elif (sumN - 2) % 2 == M % 2:
		if gcd((sumN - M) // 2, (sumN + M) // 2) == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
while t:
	f = 0
	(n, m) = map(int, input().split())
	k = n * (n + 1) // 2
	if (k - m) % 2 == 0:
		if gcd((k - m) // 2, (k - m) // 2 + m) == 1:
			f = 1
	if f == 0:
		print('No')
	else:
		print('Yes')
	t = t - 1


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for i in range(t):
	(N, M) = map(int, input().split())
	ts = N * (N + 1) // 2
	s1 = (ts + M) // 2
	s2 = ts - s1
	a = gcd(s1, s2)
	m = max(s1, s2) - min(s1, s2)
	if M > ts or m != M or a != 1:
		print('No')
	else:
		print('Yes')


t = int(input().strip())

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(t):
	(n, m) = [int(i) for i in input().strip().split(' ')]
	s = n * (n + 1) // 2
	if m >= s:
		print('No')
		continue
	a = (m + s) // 2
	b = (s - m) // 2
	if a + b != s or a - b != m:
		print('No')
		continue
	if gcd(a, b) == 1:
		print('Yes')
	else:
		print('No')


def gcd(a, b):
	if not a:
		return b
	else:
		return gcd(b % a, a)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	nSum = n * (n + 1) // 2
	t = nSum - m
	if t > 0 and t % 2 == 0:
		s1 = s2 = t // 2
		s1 += m
		if gcd(s1, s2) == 1:
			print('Yes')
			continue
	print('No')


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
T = int(input())
for y in range(T):
	(N, M) = map(int, input().split())
	total_sum = N * (N + 1) // 2
	sum1 = M + total_sum
	if sum1 % 2 == 0:
		sum1 //= 2
		sum2 = total_sum - sum1
		if gcd(sum1, sum2) == 1:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


from fractions import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = n * (n + 1) // 2
	(ai, bi) = (m + p, p - m)
	if 1 in (ai % 2, bi % 2):
		print('No')
	else:
		a = ai // 2
		b = bi // 2
		if gcd(a, b) > 1:
			print('No')
		else:
			print('Yes')


from math import gcd
for t in range(int(input())):
	(n, m) = map(int, input().split())
	tot = n * (n + 1) // 2
	f = True
	if (tot + m) % 2 != 0 or (tot - m) % 2 != 0:
		f = False
	if f:
		a = (tot + m) // 2
		b = (tot - m) // 2
		if b < 0:
			f = False
		elif gcd(a, b) != 1:
			f = False
	if f:
		print('Yes')
	else:
		print('No')


import sys
import math
from fractions import gcd
mod = 1000000007

def nospace(l):
	ans = ''.join((str(i) for i in l))
	return ans
t = int(input())
for tt in range(t):
	a = list(map(int, sys.stdin.readline().split(' ')))
	n = a[0]
	m = a[1]
	if (n * (n + 1) // 2 + m) % 2:
		print('No')
		continue
	s1 = (n * (n + 1) // 2 + m) // 2
	s2 = n * (n + 1) // 2 - s1
	if s2 == 0:
		if s1 == 1:
			print('Yes')
		else:
			print('No')
		continue
	if s2 < 0:
		print('No')
		continue
	if gcd(s1, s2) == 1:
		print('Yes')
	else:
		print('No')


from math import gcd
t = int(input())
while t:
	t -= 1
	(n, m) = list(map(int, input().split()))
	n = n * (n + 1) // 2
	if (n - m) % 2:
		print('No')
	else:
		a = (n - m) // 2
		if gcd(a, a + m) != 1:
			print('No')
		else:
			print('Yes')