import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc= new Scanner(System.in);
int k= sc.nextInt();
for(int j=0;j<k;j++)
{int n= sc.nextInt();
int m= sc.nextInt();
int sum=0;
for(int i=1;i<=n;i++)
{sum= sum+ (int)Math.pow(i,i);
}
int l=sum%m;
System.out.println(l);
}
}
}