#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qpow(LL a, LL b, LL c)
{
    LL ret = 1 % c; a = a % c;
    for (; b; b >>= 1, a = a * a % c) if (b & 1) ret = ret * a % c;
    return ret;
}
int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        int n; LL c; scanf("%lld%d", &c, &n);
        LL ans = 0;
        for (LL i = 1, a, b; i <= n; i++)
        {
            scanf("%lld%lld", &a, &b);
            ans = (ans + qpow(a, b, c)) % c;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qpow(LL a,LL b,LL c)
{
	LL ret=1%c; a=a%c;
	for(;b;b>>=1,a=a*a%c)if(b&1)ret=ret*a%c;
	return ret;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;LL c;scanf("%lld%d",&c,&n);
        LL ans=0;
        for(LL i=1,a,b;i<=n;i++)
        {
            scanf("%lld%lld",&a,&b);
            ans=(ans+qpow(a,b,c))%c;
        }
        printf("%lld\n",ans);
    }
    return 0;
}