t = int(input())
for i in range(t):
    n,m = map(int, input().split())
    ans = n
    if ans % 2 == 0:
        ans //= 2
        ans %= m
        ans *= n + 1
    else:
        ans %= m
        ans *= ((n + 1) // 2) % m
    ans %= m
    print(ans)