#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;

// dzielnik[i] = dowolny dzielnik pierwszy liczby i
int dzielnik[MAXN];
// gdzieLewo[p] = pierwszy indeks,
// na ktorym liczba jest podzielna przez p (pierwsze)
int gdzieLewo[MAXN];
// gdziePrawo[p] = ostatni indeks,
// na ktorym liczba jest podzielna przez p (pierwsze)
int gdziePrawo[MAXN];

int ilePrzedzialow[MAXN];

void sito()
{
	for (int i = 2; i*i < MAXN; ++i) {
		if (dzielnik[i] == 0) {
			for (int j = i*i; j < MAXN; j += i)
				dzielnik[j] = i;
		}
	}
	for (int i = 2; i < MAXN; ++i) {
		if (dzielnik[i] == 0)
			dzielnik[i] = i;
	}
}

void solve()
{
	// zerowanie tablic
	for (int i = 0; i < MAXN; ++i) {
		gdzieLewo[i] = MAXN - 1; // [MAXN-1, 0]
		gdziePrawo[i] = 0;
		ilePrzedzialow[i] = 0;
	}

	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int a;
		cin >> a;
		// rozklad liczby a na czynniki pierwsze
		while (a > 1) {
			int p = dzielnik[a];
			gdzieLewo[p] = min(gdzieLewo[p], i);
			gdziePrawo[p] = max(gdziePrawo[p], i);
			a /= p;
		}
	}

	for (int i = 2; i < MAXN; ++i) {
		int l = gdzieLewo[i];
		int r = gdziePrawo[i];
		if (l <= r) {
			ilePrzedzialow[l] += 1;
			ilePrzedzialow[r] -= 1;
		}
	}
	for (int i = 1; i <= n; ++i)
		ilePrzedzialow[i] += ilePrzedzialow[i - 1];

	for (int i = 1; i < n; ++i) {
		if (ilePrzedzialow[i] == 0) {
			cout << i << '\n';
			return;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	sito();

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
		solve();
	return 0;
}