/*
Getting a modulo from big number is possible in O(length of number * 10)
by multiplying current modulo by 10 and adding next digit. 
Raising to power is similar. Getting A*B%C if A, B, C <= 10**18 can be done by binary multiplication.
*/


#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <string.h>
#include <set>
#include <map>
#include <stdlib.h>
#include <iomanip>
#include <bitset>
#include <cmath>

using namespace std;

long long MOD;
long long mult(long long A, long long B)
{
	if ( B == 0 ) return 0;
	long long u = mult(A, B/2);
	long long res;
	if ( B%2 == 0 ) 
		res = u + u;
	else
		res = u + u + A;
	while ( res >= MOD ) res -= MOD;
	return res;
}

char s[10100];
void solve()
{
	cin>>MOD;
	cin>>s;
	int l = strlen(s);
	long long ans = 1%MOD;
	for (int i=0; i<l; i++)
	{
		long long F = 0;
		int j = i;
		while ( s[j] >= '0' && s[j] <= '9' ) 
		{
			F = mult(F, 10);
			F += s[j]-'0';
			F %= MOD;
			j++;
		}
		j++;
		j++;
		long long NF = 1%MOD;
		while ( s[j] >= '0' && s[j] <= '9' ) 
		{
			long long WNF = 1;
			for (int k=1; k<=10; k++)
				WNF = mult(NF, WNF);
			NF = WNF;
			for (int k=1; k <= s[j]-'0'; k++)
				NF = mult(NF, F);
			j++;
		}
		//cout<<NF<<endl;
		ans = mult(ans, NF);
		i = j;
	}
	cout<<ans<<"\n";
}
int main()
{
	//freopen("in3.txt", "r", stdin);
	//freopen("out3.txt", "w", stdout);
	int test;
	cin>>test;
	while ( test-- ) solve();
	return 0;
}