#include<stdio.h>
#define MAX 45000+20
typedef long long ll;
ll a[MAX];
ll b[MAX];
ll qmod(ll a,ll b,ll c)
{
	ll ans=1;
	a=a%c;
	while(b>0)
	{
		if(b&1)
		ans=ans*a%c;
		a=a*a%c;
		b>>=1;
	}
	return ans;
}
int main()
{
	int t;
	ll c;
	int n;
	while(~scanf("%d",&t))
	{
		for(int k=0;k<t;k++)
		{
			scanf("%I64d %d",&c,&n);
			ll ans=0;
			ll res;
			for(int i=0;i<n;i++)
			{
				scanf("%I64d %I64d",&a[i],&b[i]);
				res=qmod(a[i],b[i],c);
				ans=(ans+res)%c;
			}
			ans=ans%c;
			printf("%I64d\n",ans);
		}
	}
}