#include <iostream>
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <stdint.h>
#include <bitset>

using namespace std;

const int UPPER_LIMIT = 1000000;

std::vector<int> primes;

void genPrimes(int max){

    char *sieve;
    sieve = new char[max/2+1];
    // Fill sieve with 1
    memset(sieve, 0xFF, (max/2+1) * sizeof(char));
    for(int x = 2; x <= max; x++)
        if(sieve[x/8] & (0x01 << (x % 8))){
            primes.push_back(x);
            // Is prime. Mark multiplicates.
            for(int j = 2*x; j <= max; j += x)
                sieve[j/8] &= ~(0x01 << (j % 8));
        }
    delete[] sieve;
}

int main() {

    primes.reserve(UPPER_LIMIT + 1);
    genPrimes(UPPER_LIMIT + 1);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        bitset<UPPER_LIMIT + 1> table;

        int maxPrime = 0;

        while (n--) {
            int tmp;
            cin >> tmp;

            if (binary_search(primes.begin(), primes.end(), tmp)) {
                table[1 + distance(primes.begin(), lower_bound(primes.begin(), primes.end(), tmp))] = true;
                // cout << "p = " << 1 + distance(primes.begin(), lower_bound(primes.begin(), primes.end(), tmp)) << '\n';
                maxPrime = max(maxPrime, tmp);
            }
            else
            if (tmp == 1) {
                table[0] = true;
            }
        }

        // testa se a sequencia 1, 2, 3, 5, 7, ..., maxPrime foi lida
        int pos = maxPrime > 0 ? 1 + distance(primes.begin(), lower_bound(primes.begin(), primes.end(), maxPrime)) : 0;
        bool flag = true;
        while (pos >= 0) flag &= table[pos--];

        cout << (flag ? (*upper_bound(primes.begin(), primes.end(), maxPrime) - 1) : 0) << '\n';
    }

    return 0;
}