# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")
from collections import *
from functools import *
from itertools import *
from heapq import *
import sys, math,random,time
# input = sys.stdin.readline


def answer():
    N,M = map(int,input().split())
    print(N*(N+1)//2%M)
for _ in range(int(input())):
    answer()