```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MAX_VAL = 1000001
const INF = 1000000000

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &a[i])
	}

	// Sieve to find Smallest Prime Factor (SPF) for every number up to MAX_VAL
	spf := make([]int, MAX_VAL)
	for i := 0; i < MAX_VAL; i++ {
		spf[i] = i
	}
	for i := 2; i*i < MAX_VAL; i++ {
		if spf[i] == i {
			for j := i * i; j < MAX_VAL; j += i {
				if spf[j] == j {
					spf[j] = i
				}
			}
		}
	}

	adj := make([][]int, MAX_VAL)
	seen := make(map[int]bool)

	// Process each number to its square-free part and build the graph
	for _, x := range a {
		val := x
		b := 1
		// Calculate square-free part
		for val > 1 {
			p := spf[val]
			cnt := 0
			for val%p == 0 {
				cnt++
				val /= p
			}
			if cnt%2 == 1 {
				b *= p
			}
		}

		// If square-free part is 1, the number itself is a perfect square
		if b == 1 {
			fmt.Fprintln(out, 1)
			return
		}
		// If we have seen this square-free part before, product of two same numbers is a square
		if seen[b] {
			fmt.Fprintln(out, 2)
			return
		}
		seen[b] = true

		// Factorize b (which is square-free) into primes.
		// Since original numbers have at most 7 divisors, b has at most 2 prime factors.
		p1 := spf[b]
		p2 := b / p1
		u, v := 0, 0
		if p2 == 1 {
			u, v = 1, p1
		} else {
			u, v = p1, p2
		}
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	minLen := INF
	dist := make([]int, MAX_VAL)
	par := make([]int, MAX_VAL)
	for i := range dist {
		dist[i] = -1
	}

	q := make([]int, 0, MAX_VAL)
	visitedList := make([]int, 0, MAX_VAL)

	// BFS from every "small" node (1 and primes <= 1000)
	// Any cycle in the graph must involve at least one such node.
	for i := 1; i <= 1000; i++ {
		if len(adj[i]) == 0 {
			continue
		}

		q = q[:0]
		visitedList = visitedList[:0]

		dist[i] = 0
		par[i] = -1
		q = append(q, i)
		visitedList = append(visitedList, i)

		head := 0
		for head < len(q) {
			u := q[head]
			head++
			d := dist[u]

			// Pruning: if the shortest possible cycle from this depth is not better than current best, stop.
			if d*2+1 >= minLen {
				break
			}

			for _, v := range adj[u] {
				if dist[v] == -1 {
					dist[v] = d + 1
					par[v] = u
					q = append(q, v)
					visitedList = append(visitedList, v)
				} else {
					if v != par[u] {
						// Cycle detected
						curLen := d + dist[v] + 1
						if curLen < minLen {
							minLen = curLen
						}
						// Smallest possible cycle length > 2 is 3.
						if minLen == 3 {
							fmt.Fprintln(out, 3)
							return
						}
					}
				}
			}
		}

		// Reset dist array for visited nodes
		for _, v := range visitedList {
			dist[v] = -1
		}
	}

	if minLen == INF {
		fmt.Fprintln(out, -1)
	} else {
		fmt.Fprintln(out, minLen)
	}
}
```