//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 1e6 + 10;
int n, dis[N], ism[N], cnt = 0, prime[N], mi[N], stk[N], tp = 0;
int used[N], su[N], k = 0;
void Sieve(int mx)
{
	ism[1] = 1;
	for (int i = 2; i <= mx; ++i)
	{
		if (!ism[i])
		{
			prime[++cnt] = i;
			mi[i] = i;
		}
		for (int j = 1; j <= cnt && i * prime[j] <= mx; ++j)
		{
			ism[i * prime[j]] = 1;
			mi[i * prime[j]] = prime[j];
			if (i % prime[j] == 0)
				break;
		}
	}
}
vector<pair<int, int> > G[N];
queue<int> q;
int main()
{
	n = read();
	Sieve(1000000);
	int m = 0;
	for (int i = 1; i <= n; ++i)
	{
		int v = read(), x = 1, y = 1;
		while (v > 1)
		{
			int p = mi[v], t = 0;
			while (v % p == 0)
				v /= p, t ^= 1;
			if (t & 1)
			{
				if (x == 1)
					x = p;
				else if (y == 1)
					y = p;
				else
					assert(false);
			}
		}
		++m;
		G[x].push_back(make_pair(y, m)), G[y].push_back(make_pair(x, m));
	}
	memset(dis, -1, sizeof dis);
	prime[0] = 1;
	int ans = n + 1;
	for (int i = 0; i <= cnt && prime[i] <= 1000; ++i)
	{
		while (tp)
			dis[stk[tp--]] = -1;
		while (k)
			used[su[k--]] = 0;
		int s = prime[i];
		dis[s] = 0, q.push(s), stk[++tp] = s;
		while (!q.empty())
		{
			int x = q.front();
			q.pop();
			if (dis[x] + 1 >= ans)
				continue;
			for (auto tmp : G[x])
				if (!used[tmp.second])
				{
					int y = tmp.first;
					if (dis[y] != -1)
						ans = min(ans, dis[x] + dis[y] + 1);
					else
					{
						dis[y] = dis[x] + 1;
						q.push(y), stk[++tp] = y;
						used[tmp.second] = 1, su[++k] = tmp.second;
					}
				}
		}
	}
	if (ans > n)
		puts("-1");
	else
		write(ans, '\n');
	return 0;
}