#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <limits>
#include <numeric>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define MP make_pair
#define all(v) (v).begin(), (v).end()

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef long double ld;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef pair<ll, ll> pll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;

ll CountLeq(ll x, int power) {
  if (power == 1) {
    return x - 1;
  }
  double t = pow(double(x), 1.0 / power);
  for (int ans = ceil(t) + 2; ; --ans) {
    ll powans = 1;
    bool good = true;
    for (int i = 1; i <= power; ++i) {
      if (x / ans >= powans) {
        powans *= ans;
      } else {
        good = false;
        break;
      }
    }
    if (good && powans <= x) {
      return ans - 1;
    }
  }
}

ll CountLeq(ll x, const vi& coeffs) {
  if (x == 1) {
    return 1;
  }
  ll result = 1;
  for (int i = 1; i < coeffs.size(); ++i) {
    if (coeffs[i]) {
      result += CountLeq(x, i) * coeffs[i];
    }
  }
  return result;
}

int main() {
  int tests;
  cin >> tests;
  for (int test_index = 0; test_index < tests; ++test_index) {
    int N, m;
    scanf("%d%d", &N, &m);
    vi pows(m);
    for (int i = 0; i < m; ++i) {
      scanf("%d", &pows[i]);
    }
    sort(pows.begin(), pows.end());
    vb is_needed(61, false);
    for (int i = 0; i < pows.size(); ++i) {
      for (int j = 1; j * pows[i] < 61; ++j) {
        is_needed[j * pows[i]] = true;
      }
    }
    vi coeffs(61, 0);
    for (int i = 1; i < 61; ++i) {
      if (!is_needed[i]) {
        continue;
      }
      int sum = 0;
      for (int j = 1; j < i; ++j) {
        if (i % j == 0) {
          sum += coeffs[j];
        }
      }
      coeffs[i] = 1 - sum;
    }
    ll low = 1;
    ll high = ll(1000000000) * ll(100000000);
    while (low < high) {
      ll mid = (low + high) / 2;
      ll less_x = CountLeq(mid, coeffs);
      if (less_x < N) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }   
    cout << low << endl;
  }
  return 0;
}