import sys

inf = float("inf")

input = lambda: sys.stdin.readline().rstrip("\r\n")

print = lambda *args, end="\n", sep=" ": sys.stdout.write(
    sep.join(map(str, args)) + end
)


def II():
    return int(input())


def MII(b=0):
    return map(lambda x: int(x) - b, input().split())


def LII(b=0):
    return list(MII(b))


class Decimal:
    def __init__(self, num_str):
        self.digits = [int(digit) for digit in num_str[::-1]]

    def __add__(self, other):
        result = []
        carry = 0
        max_len = max(len(self.digits), len(other.digits))

        for i in range(max_len):
            a = self.digits[i] if i < len(self.digits) else 0
            b = other.digits[i] if i < len(other.digits) else 0
            temp = a + b + carry
            result.append(temp % 10)
            carry = temp // 10

        if carry:
            result.append(carry)

        return Decimal("".join(map(str, result[::-1])))

    def __mod__(self, n):
        remainder = 0
        for digit in self.digits[::-1]:
            remainder = (remainder * 10 + digit) % n
        return remainder


num1 = Decimal("123")
num2 = Decimal("456")

sum_result = num1 + num2
mod_result = num1 % 7


for _ in range(II()):
    x, m = input().split()
    m = int(m)
    x = Decimal(x)
    y = x + Decimal("1")

    m *= 2
    print(((x % m) * (y % m) % m) // 2)