#include <stdio.h>
__int64 rmq(__int64 a,__int64 b,__int64 m)
{
   __int64 sum=1;
   while(b)
   {
   	if(b&1)
   	sum=(a*sum)%m;
   	b/=2;
   	a=(a%m)*(a%m)%m;
   }
   return sum;
}
int main()
{
int cases,n;
__int64 m,a,b,total;
scanf("%d",&cases);
while(cases--)
{
	scanf("%I64d",&m);
	scanf("%d",&n);
	total=0;
	while(n--)
	{
		scanf("%I64d%I64d",&a,&b);
		total+=rmq(a,b,m);
	}
	printf("%I64d\n",total%m);
}
return 1;
}