#include <iostream>

 #include <functional>

 #include <algorithm>

 using namespace std;

 typedef long long LL_INT;

 LL_INT cal(const LL_INT, const LL_INT, const LL_INT);

 int main(void)

 {

     int case_sum, item_sum;

     LL_INT mod, a, b, sum;

     scanf("%d", &case_sum);

     while (case_sum--)

     {

         sum = ;

         scanf("%lld%d", &mod, &item_sum);

         for (int i = ; i < item_sum; i++)

         {

             scanf("%lld%lld", &a, &b);

             sum = (sum + cal(a, b, mod)) % mod;

         }

         printf("%lld\n", sum);

     }

     return ;

 }

 LL_INT cal(const LL_INT coe, const LL_INT pow, const LL_INT mod)

 {

     LL_INT x, y;

     if (!pow)

         return ;

     x = cal(coe, pow >> , mod);

     y = (x*x) % mod;

     if (pow % )

         y = (coe*y) % mod;

     return y;

 }