Ichigo is on his way to save Rukia. Unfortunately, when Ichigo was busy fighting Renji, Kenpachi Zaraki had gone to the Dangai(the same place where Ichigo got his final Getsuga Tenshou) to train. Now, he has a Bankai called Tensa Quantum Computer and he used it against Ichigo!

Tensa Quantum Computer consists of 2N rooms arranged in a circle. Kenpachi imprisoned Rukia in one of these rooms. The rooms have the numbers 1, 2, ..., N-1, N, -N, -(N-1), ..., -1 written on them in that order clockwise. Each room has a one-way door to another unique room. Kenpachi knows that if a room has number X, then it leads to another room which is at distance abs(X) from this room. More precisely, if X is positive, it means that this room leads to the X-th room in the clockwise direction from the current room. And if X is negative, then that means that this room leads to the (-X)-th room in the anticlockwise direction from the current room.

Kenpachi knows that Ichigo starts at the room with the number A. Being a determined guy, Ichigo doesn't sit still until he finds Rukia. Instead he keeps running to the next room for as long as he can. But Kenpachi's funny and crafty lieutenant Yachiru Kusajishi suggested that if Kenpachi keeps Rukia in one of the rooms that Ichigo will never visit, then Ichigo will keep running forever and die from exhaustion.

Now, Kenpachi wants to know the number of rooms that he can keep Rukia in, so that poor Ichigo never finds her and hence, keeps running.

Note: abs(X) is the absolute value of X.

Input Format

Line 1: T 

T - Number of test cases. 

Lines 2 to T+1: N A 

N - Half the total number of rooms. 

A - The number of the room where Ichigo starts his pursuit of Rukia.  

Output Format

For each test case, print a single integer in a new line that is the number of rooms where Kenpachi can imprison Rukia so that Ichigo never finds her.

Constraints

1 <= T <= 1000 

1 <= N <= 10^{9} 

1 <= abs(A) <= N

Sample Input

4
1 1
4 1
4 -3
1729 -786

Sample Output

0
2
6
3170

Explanation

In the first test case, the rooms that Ichigo visits have numbers 1, -1, 1, -1, ... in that order. So, there are no unvisited rooms. 

In the second test case, the rooms that Ichigo visits have numbers 1, 2, 4, -1, -2, -4, 1, 2, ... in that order. So, there are two unvisited rooms namely the ones numbered 3 and -3. 

In the third test case, the rooms that Ichigo visits have numbers -3, 3, -3, 3, ... in that order. So, there are six unvisited rooms namely the ones numbered 1, 2, 4, -4, -2, -1.

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
import math

def sieve(lim):
	primes = [2]
	mark = bytearray(lim)
	for i in range(3, lim, 2):
		if mark[i]:
			continue
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j] = 1
	return primes
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
T = int(input())
for t in range(T):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


import os, sys, math, itertools
from collections import Counter

def prime_factorization(x):
	assert x > 0
	counts = Counter()
	p = 2
	while x != 1:
		while True:
			(q, r) = divmod(x, p)
			if r != 0:
				break
			counts[p] += 1
			x = q
		p = 3 if p == 2 else p + 2
		if p * p > x:
			break
	if x != 1:
		counts[x] += 1
	return counts

def totient(n):
	s = n
	d = 2
	while d * d <= n:
		if n % d == 0:
			while n % d == 0:
				n //= d
			s -= s // d
		d += 1
	if n > 1:
		s -= s // n
	return s

def modular_power(a, n, m):
	if n == 0:
		return 1
	a = a % m
	if a < 0:
		a += m
	prod = 1
	pwr = a
	while n != 0:
		if n % 2 != 0:
			prod = prod * pwr % m
		n >>= 1
		if n == 0:
			break
		pwr = pwr * pwr % m
	return prod

def modular_period(a, m):
	nz = totient(m)
	if a == 1:
		return 1
	pf = prime_factorization(nz)
	pf = [(p, c) for (p, c) in pf.items()]
	pf.sort()
	emaxes = tuple([range(c + 1) for (_, c) in pf])
	divs = []
	for exps in itertools.product(*emaxes):
		s = sum(exps)
		if s == 0:
			continue
		divs.append((s, exps))
	divs.sort()
	for (_, exps) in divs:
		x = a
		for ((p, _), k) in zip(pf, exps):
			if k == 0:
				continue
			for _ in range(k):
				x = modular_power(x, p, m)
		if x == 1:
			e = 1
			for ((p, _), k) in zip(pf, exps):
				if k == 0:
					continue
				e *= p ** k
			return e
	return -1

def solveCases(cases):
	modular_period_cache = {}

	def modular_period_c(a, m):
		y = modular_period_cache.get((a, m))
		if y is None:
			y = modular_period_cache[a, m] = modular_period(a, m)
		return y
	answers = []
	for (n, a) in cases:
		nr = 2 * n + 1
		p = modular_period_c(2, nr // math.gcd(nr, a))
		answers.append(2 * n - p)
	return answers

def main():
	t = int(sys.stdin.readline())
	cases = []
	for _ in range(t):
		cases.append(list(map(int, sys.stdin.readline().split())))
	for result in solveCases(cases):
		print(result)
main()


import math

def sieve(limit):
	prime = [2]
	mark = bytearray(limit)
	for i in range(3, limit, 2):
		if mark[i]:
			continue
		prime.append(i)
		for j in range(3 * i, limit, 2 * i):
			mark[j] = 1
	return prime
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
number_of_cases = int(input())
for t in range(number_of_cases):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


import sys
sys.setrecursionlimit(10000)

def primes(n):
	(f, rs, M) = ([4294967295] * (n + 1 + 63 >> 6), [2], [1 << (i >> 1) for i in range(64)])
	for i in range(3, n + 1, 2):
		if f[i >> 6] & M[i & 63]:
			rs.append(i)
		for j in range(1, len(rs)):
			pi = rs[j] * i
			if pi > n:
				break
			if f[pi >> 6] & M[pi & 63]:
				f[pi >> 6] -= M[pi & 63]
			if i % rs[j] == 0:
				break
	return rs
T = int(input())
A = [None] * T
N = [None] * T
i = 0
while i < T:
	(N[i], A[i]) = map(int, input().split(' '))
	i += 1
MAXN2 = int((2 * max(N) + 1) ** 0.5 + 0.0001)
if MAXN2 < 100:
	MAXN2 = 100
PS = primes(MAXN2)
PSL = len(PS)
PF = {1: {}}

def merger(a, b):
	for (p, c) in a.items():
		if p in b:
			a[p] += b[p]
	for (p, c) in b.items():
		if p not in a:
			a[p] = c

def powM(b, e, M):
	r = 1
	while e:
		if e & 1:
			r = r * b % M
		b = b * b % M
		e >>= 1
	return r

def fact(n):
	r = {}
	ip = 0
	while True:
		if ip == PSL or PS[ip] ** 2 > n:
			r[n] = 1
			return r
		p = PS[ip]
		if n % p == 0:
			c = 1
			n //= p
			while n % p == 0:
				c += 1
				n //= p
			r[p] = c
			if n == 1:
				return r
		ip += 1

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

def phiFact(n):
	if n in PF:
		return PF[n]
	r = {}
	PF[n] = r
	for (p, c) in fact(n).items():
		if c > 1:
			if p in r:
				r[p] += c - 1
			else:
				r[p] = c - 1
		if p > 2:
			merger(r, fact(p - 1))
	return r
import math
PCC = [None] * 100
for p in range(2, 100):
	if p in PS:
		PCC[p] = [p ** i for i in range(int(math.log(10 ** 9, p) + 1))]
import heapq

def allfact(pf):
	pf = list(pf.items())
	pl = len(pf)
	PM = [None] * pl
	PP = [None] * pl
	i = 0
	H = [1]
	heapq.heapify(H)
	while i < pl:
		(p, c) = pf[i]
		PM[i] = PCC[p][c] if p < 100 else p ** c
		PP[i] = p
		i += 1
	prev = 0
	while H:
		v = heapq.heappop(H)
		if v == prev:
			continue
		prev = v
		yield v
		i = 0
		while i < pl:
			if v % PM[i] != 0:
				heapq.heappush(H, v * PP[i])
			i += 1

def solution(n, a):
	n21 = n + n + 1
	if a < 0:
		a = 2 * n + 1 + a
	n21 = n21 // gcd(a, n21)
	pf = phiFact(n21)
	for f in allfact(pf):
		if powM(2, f, n21) == 1:
			print(n + n - f)
			break
for i in range(T):
	solution(N[i], A[i])


def gcd(a, b):
	while b > 0:
		c = a % b
		a = b
		b = c
	return a

def sieve():
	arr = [1 for i in range(44720)]
	arr.insert(0, 0)
	arr.insert(0, 0)
	ps = []
	l = len(arr)
	sq = 0
	for (i, val) in enumerate(arr):
		if sq ** 2 > 2000000001:
			break
		elif val == 1:
			ind = i
			ps.append(i)
			for ind in range(sq, l, i):
				arr[ind] = 0
		sq = sq + 2 * i + 1
	for j in range(i, l):
		if arr[j] == 1:
			ps.append(j)
	return ps

def sieve_factor(n, primes):
	d = dict()
	for div in primes:
		while n % div == 0:
			if div in d:
				d[div] += 1
			else:
				d[div] = 1
			n = n // div
		if n == 1:
			break
	if n != 1:
		d[n] = 1
	return d

def phi(d):
	ans = 1
	for (prime, exp) in d.items():
		ans = ans * (prime - 1) * pow(prime, exp - 1)
	return ans
primes = sieve()

def order(g, n, d, primes):
	h = phi(d)
	d2 = sieve_factor(h, primes)
	e = h
	for (pi, vi) in d2.items():
		e = e // pow(pi, vi)
		g1 = pow(2, e, n)
		while g1 * g % n != g:
			g1 = pow(g1, pi, n)
			e = e * pi
	return e
for _ in range(int(input())):
	(n, a) = list(map(int, input().split()))
	a = abs(a)
	num = 2 * n + 1
	g = gcd(num, a)
	num2 = num // g
	a = a // g
	d = sieve_factor(num2, primes)
	visited = order(a, num2, d, primes)
	print(num - visited - 1)


from functools import reduce

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
lcm = lambda a, b: a * b / gcd(a, b)

def isPrime(p):
	return p > 1 and all((f == p for (f, e) in factored(p)))
primeList = [2, 3, 5, 7]

def primes():
	for p in primeList:
		yield p
	while 1:
		p += 2
		while not isPrime(p):
			p += 2
		primeList.append(p)
		yield p

def factored(a):
	for p in primes():
		j = 0
		while a % p == 0:
			a /= p
			j += 1
		if j > 0:
			yield (int(p), j)
		if a < p * p:
			break
	if a > 1:
		yield (int(a), 1)
phi = lambda prime, exp: (prime - 1) * prime ** (exp - 1)

def multOrdr1(number, prime, exp):
	qs = [1]
	for (p, e) in factored(phi(prime, exp)):
		qs = [q * p ** j for j in range(1 + e) for q in qs]
	m = prime ** exp
	for q in qs:
		if pow(number, q, m) == 1:
			break
	return q

def multOrder(a, m):
	assert gcd(a, m) == 1
	mofs = (multOrdr1(a, p, e) for (p, e) in factored(m))
	return reduce(lcm, mofs, 1)

def getMissing(N, start):
	M = 2 * N + 1
	start += int(start < 0) * M
	g = gcd(M, start)
	m = M // g
	return 2 * N - int(multOrder(2, m))
T = int(input())
for _ in range(T):
	(N, start) = list(map(int, input().strip().split()))
	result = getMissing(N, start)
	print(result)


import math
isprime = [True] * 32000
primelist = []
for i in range(2, 32000):
	if isprime[i]:
		primelist.append(i)
		for j in range(i * i, 32000, i):
			isprime[j] = False

def ordnum(base, m, tot):
	toret = tot
	curr = tot
	for p in primelist:
		while toret % p == 0:
			cand = toret // p
			if pow(base, cand, m) == 1:
				toret = cand
			else:
				break
		while curr % p == 0:
			curr = curr // p
	if curr != 1:
		cand = toret // curr
		if pow(base, cand, m) == 1:
			toret = cand
	return toret
t = int(input())
for _ in range(t):
	(n, a) = list(map(int, input().split(' ')))
	rn = 2 * n + 1
	rn = rn // math.gcd(rn, a)
	ord2 = 1
	curr = rn
	for p in primelist:
		if rn % p == 0:
			curr = curr // p
			ppow = p
			tot = p - 1
			while curr % p == 0:
				ppow *= p
				tot *= p
				curr //= p
			temp = ordnum(2, ppow, tot)
			ord2 = ord2 * temp // math.gcd(ord2, temp)
	if curr != 1:
		temp = ordnum(2, curr, curr - 1)
		ord2 = ord2 * temp // math.gcd(ord2, temp)
	print(2 * n - ord2)


from fractions import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


from fractions import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


from fractions import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


from fractions import gcd
import math
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= math.gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


from fractions import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


from fractions import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


from fractions import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


import math

def sieve(lim):
	primes = [2]
	mark = bytearray(lim)
	for i in range(3, lim, 2):
		if mark[i]:
			continue
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j] = 1
	return primes
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
T = int(input())
for t in range(T):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


import math

def sieve(lim):
	primes = [2]
	mark = bytearray(lim)
	for i in range(3, lim, 2):
		if mark[i]:
			continue
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j] = 1
	return primes
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
T = int(input())
for t in range(T):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


import math
from math import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break


import math

def sieve(lim):
	primes = [2]
	mark = bytearray(lim)
	for i in range(3, lim, 2):
		if mark[i]:
			continue
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j] = 1
	return primes
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
T = int(input())
for t in range(T):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


import math

def sieve(lim):
	primes = [2]
	mark = bytearray(lim)
	for i in range(3, lim, 2):
		if mark[i]:
			continue
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j] = 1
	return primes
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
T = int(input())
for t in range(T):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


import math

def sieve(lim):
	primes = [2]
	mark = bytearray(lim)
	for i in range(3, lim, 2):
		if mark[i]:
			continue
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j] = 1
	return primes
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
T = int(input())
for t in range(T):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


import math

def sieve(lim):
	primes = [2]
	mark = bytearray(lim)
	for i in range(3, lim, 2):
		if mark[i]:
			continue
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j] = 1
	return primes
primes = sieve(45000)

def factor(n):
	f = {}
	for p in primes:
		if p * p > n:
			break
		while n % p == 0:
			n //= p
			f[p] = f.get(p, 0) + 1
	if n > 1:
		f[n] = 1
	return f

def totient(n):
	f = factor(n)
	t = 1
	for p in f:
		t *= (p - 1) * p ** (f[p] - 1)
	return t
T = int(input())
for t in range(T):
	(N, A) = map(int, input().split())
	m = 2 * N + 1
	m //= math.gcd(m, A % m)
	t = totient(m)
	for p in factor(t):
		while t % p == 0 and pow(2, t // p, m) == 1:
			t //= p
	print(2 * N - t)


from math import gcd
lim = 111111
primes = [0] * 2 + [1] * (lim - 2)
pc = 0
for i in range(2, lim):
	if primes[i]:
		primes[pc] = i
		pc += 1
		for j in range(i * i, lim, i):
			primes[j] = 0

def prime_fac(n):
	if n == 1:
		return
	for pi in range(pc):
		p = primes[pi]
		if p * p > n:
			p = n
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e:
			yield (p, e)
		if n == 1:
			break

def phi(n):
	for (p, e) in prime_fac(n):
		n -= n // p
	return n
divs = [1] * lim

def divisors(n):
	yield (1, 1)
	dc = 1
	for (p, e) in prime_fac(n):
		odc = dc
		for t in range(odc * e):
			old = divs[dc - odc]
			new = divs[dc] = old * p
			dc += 1
			yield (new, old)
z = int(input())
assert 1 <= z <= 1000
for cas in range(z):
	(n, a) = map(int, input().strip().split())
	assert 1 <= n <= 10 ** 9 and 1 <= abs(a) <= n
	m = 2 * n + 1
	m //= gcd(a, m)
	dp = {}
	for (k, kold) in sorted(divisors(phi(m))):
		dp[k] = pow(dp[kold], k // kold, m) if k > 1 else 2 % m
		if dp[k] == 1:
			print(2 * n - k)
			break