using System.Numerics;
using System;

public class Hello
{
    static void Main()
    {
        var T = int.Parse(Console.ReadLine().Trim());
        while (T-- > 0)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = BigInteger.Parse(line[0]);
            var m = int.Parse(line[1]);
            getAns(n, m);
        }
    }
    static void getAns(BigInteger n, int m)
    {
        var a = n * (n + 1) / 2;
        var ans = a % m;
        Console.WriteLine(ans);
    }
}