'''
move is: a -> 2a -> 4a ... mod m , where m = (2n+1)
Task: find minimal k so that [a * 2^k = a] holds.
Answer then is:  2*n - k 
a * (2^k - 1) = 0 mod m <=> a'*g * (2^k-1) = w * m'*g  
    where g=gcd(a,m), a'*g = a, m'*g = m, w =some number
    <=> a' * (2^k-1) = w * m'
a' * (2^k-1) = 0 mod m' and gcd(a',m') = 1 = gcd(2,m')
that is: 2^k = 1 mod m' => k|phi(m')
'''

import math
from collections import Counter

N = 10**9
PRIMES = None

def main():
    for _ in range(int(input())):
        n, a = map(int, input().split())
        print(solve(n, a))

def solve(n, a):
    a, m = abs(a), 2*n+1
    g = math.gcd(a, m)
    a, m = a//g, m//g
    mf = factorize(m) 
    Kf = phi_from_fac(mf)
    for k in divs_from_fac(Kf):
        if pow(2, k, m) == 1:
            return 2*n - k
    else:
        raise RuntimeError('smells rotten')

def factorize(n):
    global PRIMES
    if not PRIMES: init_primes()
    ret = Counter()
    nroot = math.isqrt(n)
    for p in PRIMES:
        if n == 1 or p > nroot: break
        e = 0
        while n%p == 0:
            n //= p
            e += 1
        if e > 0: ret[p] = e
    if n > 1:
        ret[n] = 1
    return ret

def init_primes():
    global N, PRIMES
    cut = math.isqrt(N)
    sieve = [None] + [1] * cut
    for p in range(3, cut+1, 2):
        if sieve[p] == 0: continue
        for i in range(p*p, cut+1, 2*p):
            sieve[i] = 0
    ret = [2]
    for p in range(3, cut+1, 2):
        if sieve[p]: ret.append(p)
    PRIMES = ret

def phi_from_fac(nfac):
    ret = +nfac
    for p in nfac.keys():
        ret[p] -= 1
        ret += factorize(p-1)
    return ret

def divs_from_fac(nfac):
    ret = [1]
    for (p,e) in nfac.items():
        new = [a*p**i for a in ret for i in range(e+1)]
        ret = new
    return sorted(ret)
            
main()