#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int inf = 1e17 + 1;

int try_pow(int x, int n)
{
	int t = 1;
	for(int i = 0; i < n; i++)
	{
		t *= x;
		if(t > inf)
			return 0;
	}
	return t;
}

int rootable(int x, int n)
{
	int root = round(pow(x, 1. / n));
	return try_pow(root, n) == x;
}

int les_root(int x, int n)
{
	int root = round(pow(x, 1. / n));
	return try_pow(root, n) >= x ? root - 1 : root;
}

const int maxx = 1e5;
int uni[maxx];

signed main()
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> q;
	const int maxn = 52;
	vector<int> pw[maxn];
	for(int i = 4; i < maxn; i++)
	{
		for(int j = 1; ; j++)
			if(try_pow(j, i))
				pw[i].push_back(try_pow(j, i));
			else
				break;
	}
	while(q--)
	{
		int n, m;
		cin >> n >> m;
		int sz = 0;
		bool a1 = 0, a2 = 0, a3 = 0, a4 = 0;
		for(int i = 0; i < m; i++)
		{
			int t;
			cin >> t;
			a1 |= t == 1;
			a2 |= t == 2;
			a3 |= t == 3;
			a4 |= t == 4;
			if(t > 4)
				for(int j = 0; j < pw[t].size(); j++)
					uni[sz++] = pw[t][j];
		}
		if(a1)
		{
			cout << n << "\n";
			continue;
		}
		if(a2)
			for(int i = 0; i < sz; i++)
				if(rootable(uni[i], 2))
					uni[i] = inf;
		if(a3)
			for(int i = 0; i < sz; i++)
				if(rootable(uni[i], 3))
					uni[i] = inf;
		if(a4)
			for(int i = 0; i < sz; i++)
				if(rootable(uni[i], 4))
					uni[i] = inf;
		sort(uni, uni + sz);
		sz = unique(uni, uni + sz) - uni;
		int l = 0, r = inf;
		while(r - l > 1)
		{
			int m = (l + r) / 2;
			int pos = lower_bound(uni, uni + sz, m) - uni;
			if(a2) pos += les_root(m, 2);
			if(a3) pos += les_root(m, 3);
			if(a4) pos += les_root(m, 4);
			if(a2 && a3) pos -= les_root(m, 6);
			if(a2 && a4) pos -= les_root(m, 4);
			if(a3 && a4) pos -= les_root(m, 12);
			if(a2 && a3 && a4) pos += les_root(m, 12);
			if(pos < n)
				l = m;
			else
				r = m;
		}
		cout << l << "\n";
	}
    return 0;
}