#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>using namespace std;int n,mod,sum;int main(){    int T,a[45010],b[45010];    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&mod,&n);        int sum=0,t;        for(int i=0; i<n; i++)        {            scanf("%d%d",&a[i],&b[i]);            t=1;            while(b[i])            {                if(b[i]&1)                    t=(t*a[i])%mod;                b[i]>>=1;                a[i]=((a[i]%mod)*(a[i]%mod))%mod;            }            sum=(sum+t)%mod;        }        printf("%d\n",sum);    }    return 0;}