import sys
sys.set_int_max_str_digits(0)
def solve():
    N, M = map(int, input().split())
    if N & 1:
    	ans = N % M * ((N+1)//2 %M)
    else:
    	ans = (N//2%M)*((N+1)%M)
    print(ans%M)

def main():
    T = int(input())
    for i in range(T):
        solve()

if __name__ == '__main__':
    main()