# Enter your code here. Read input from STDIN. Print output to STDOUT
from fractions import gcd

# Sieve primes
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):
    ''' yields all prime-exponent pairs of the factorization of 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):
    ''' Euler's totient of n '''
    for p, e in prime_fac(n):
        n -= n // p
    return n

divs = [1] * lim

def divisors(n):
    ''' yields all divisors of 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