Problem: You are given an array a of length n that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square.

A sequence a is a subsequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

Input

The first line contains an integer n (1 ≤ n ≤ 10^5) — the length of a.

The second line contains n integers a_1, a_2, …, a_{n} (1 ≤ a_i ≤ 10^6) — the elements of the array a.

Output

Output the length of the shortest non-empty subsequence of a product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".

Examples

Input


3
1 4 6


Output


1

Input


4
2 3 6 6


Output


2

Input


3
6 15 10


Output


3

Input


4
2 3 5 7


Output


-1

Note

In the first sample, you can choose a subsequence [1].

In the second sample, you can choose a subsequence [6, 6].

In the third sample, you can choose a subsequence [6, 15, 10].

In the fourth sample, there is no such subsequence.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Random;
import java.util.InputMismatchException;
import java.util.TreeSet;
import java.util.ArrayList;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.Set;
import java.io.IOException;
import java.util.List;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rustam Musin (t.me/musin_acm)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    ENASTOYaShchAYaTeoriyaChiselOtYekhaba solver = new ENASTOYaShchAYaTeoriyaChiselOtYekhaba();
    solver.solve(1, in, out);
    out.close();
  }

  static class ENASTOYaShchAYaTeoriyaChiselOtYekhaba {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      if (false) {
        new Tester().test();
        return;
      }
      int n = in.readInt();
      int[] a = in.readIntArray(n);
      int answer = new Solver(a).solve();
      out.print(answer);
    }

    int[] genPrimes(int n) {
      boolean[] isPrime = new boolean[n];
      Arrays.fill(isPrime, true);
      int cnt = 0;
      for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
          cnt++;
          for (int j = i + i; j < n; j += i) {
            isPrime[j] = false;
          }
        }
      }
      int[] primes = new int[cnt];
      cnt = 0;
      for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
          primes[cnt++] = i;
        }
      }
      return primes;
    }

    class Tester {
      Random rnd = new Random();

      int divisorCount(int x) {
        int c = 0;
        for (int i = 1; i <= x; i++) {
          if (x % i == 0) {
            c++;
          }
        }
        return c;
      }

      int[] genArray(int n, int m) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
          a[i] = rnd.nextInt(m) + 1;
          if (divisorCount(a[i]) > 7) {
            i--;
          }
        }
        return a;
      }

      boolean checkArray(int[] a) {
        double x = 1;
        for (int b : a) {
          x *= b;
        }
        return x < 1e18;
      }

      void test() {
        for (int t = 0; ; t++) {
          int n = rnd.nextInt(20) + 1;
          int m = 500;
          int[] a = genArray(n, m);
          if (!checkArray(a)) {
            continue;
          }
          int solve = new Solver(a).solve();
          int naive = new Naive(a).solve();
          if (solve != naive) {
            System.err.println("Found test " + t);
            System.err.println(a.length);
            System.err.println(Arrays.toString(a));
            solve = new Solver(a).solve();
            naive = new Naive(a).solve();
          }
        }
      }

    }

    class Naive {
      int[] a;

      public Naive(int[] a) {
        this.a = a;
      }

      boolean isSquare(long x) {
        long y = Math.round(Math.sqrt(x));
        return y * y == x;
      }

      int solve() {
        int ans = Integer.MAX_VALUE;
        for (int m = 1; m < 1 << a.length; m++) {
          long x = 1;
          int bc = 0;
          for (int i = 0; i < a.length; i++) {
            if (((m >> i) & 1) == 1) {
              x *= a[i];
              bc++;
            }
          }
          if (isSquare(x)) {
            ans = Math.min(ans, bc);
          }
        }
        if (ans == Integer.MAX_VALUE) {
          ans = -1;
        }
        return ans;
      }

    }

    class Solver {
      int[] a;
      int[] primes;
      int[] primeToIndex;
      int n;
      boolean[] single;
      List<Integer>[] g;

      public Solver(int[] a) {
        this.a = a;
      }

      List<Integer> factorize(int x) {
        List<Integer> res = new ArrayList<>();
        for (int prime : primes) {
          if (prime * prime > x) {
            break;
          }
          if (x % prime == 0) {
            int power = 0;
            while (x % prime == 0) {
              x /= prime;
              power++;
            }
            if (power % 2 == 1) {
              res.add(prime);
            }
          }
        }
        if (x > 1) {
          res.add(x);
        }
        return res;
      }

      int buildGraph() {
        g = new List[n];
        for (int i = 0; i < n; i++) {
          g[i] = new ArrayList<>();
        }
        single = new boolean[n];

        boolean anySameSingle = false;
        for (int x : a) {
          List<Integer> f = factorize(x);
          if (f.isEmpty()) {
            return 1;
          }
          int u = primeToIndex[f.get(0)];
          if (f.size() == 1) {
            if (single[u]) {
              anySameSingle = true;
            } else {
              single[u] = true;
            }
          }
          if (f.size() == 2) {
            int v = primeToIndex[f.get(1)];
            g[u].add(v);
            g[v].add(u);
          }
        }

        for (int i = 0; i < n; i++) {
          Set<Integer> s = new TreeSet<>(g[i]);
          if (s.size() != g[i].size()) {
            anySameSingle = true;
          }
          g[i] = new ArrayList<>(s);
        }

        if (anySameSingle) {
          return 2;
        }
        return -1;
      }

      int solve() {
        int mx = ArrayUtils.maxElement(a);
        if (mx > 1e6) {
          throw new OutOfMemoryError("OOPS");
        }
        primes = genPrimes(mx + 1);
        n = primes.length;
        primeToIndex = new int[mx + 1];
        Arrays.fill(primeToIndex, -1);
        for (int i = 0; i < n; i++) {
          primeToIndex[primes[i]] = i;
        }

        int ans = buildGraph();
        if (ans != -1) {
          return ans;
        }
        ans = Integer.MAX_VALUE;

        BfsTree bfsTree = new BfsTree();
        for (int p : primes) {
          if (p < 1e3) {
            ans = Math.min(ans, bfsTree.getMinPath(primeToIndex[p]));
          }
        }

        if (ans == Integer.MAX_VALUE) {
          ans = -1;
        }
        return ans;
      }

      class BfsTree {
        int[] q = new int[n];
        int[] distance = new int[n];
        int[] parent = new int[n];

        void init(int start) {
          Arrays.fill(distance, -1);
          distance[start] = 0;
          parent[start] = -1;

          int qs = 0;
          q[qs++] = start;
          for (int qi = 0; qi < qs; qi++) {
            int v = q[qi];
            for (int to : g[v]) {
              if (distance[to] == -1) {
                distance[to] = distance[v] + 1;
                parent[to] = v;
                q[qs++] = to;
              }
            }
          }
        }

        int getMinPath(int start) {
          init(start);
          int res = Integer.MAX_VALUE;
          for (int from = 0; from < n; from++) {
            for (int to : g[from]) {
              if (distance[from] != -1 && distance[to] != -1 && parent[from] != to && parent[to] != from) {
                res = Math.min(res, distance[from] + distance[to] + 1);
              }
            }
          }
          List<Integer> mins = new ArrayList<>();
          for (int i = 0; i < n; i++) {
            if (single[i] && distance[i] != -1) {
              mins.add(distance[i]);
            }
          }
          mins.sort(null);
          if (mins.size() >= 2) {
            res = Math.min(res, mins.get(0) + mins.get(1) + 2);
          }
          return res;
        }

      }

    }

  }

  static class ArrayUtils {
    public static int maxElement(int[] array) {
      return new IntArray(array).max();
    }

  }

  static class IntArray extends IntAbstractStream implements IntList {
    private int[] data;

    public IntArray(int[] arr) {
      data = arr;
    }

    public int size() {
      return data.length;
    }

    public int get(int at) {
      return data[at];
    }

    public void removeAt(int index) {
      throw new UnsupportedOperationException();
    }

  }

  static interface IntReversableCollection extends IntCollection {
  }

  static abstract class IntAbstractStream implements IntStream {
    public String toString() {
      StringBuilder builder = new StringBuilder();
      boolean first = true;
      for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
        if (first) {
          first = false;
        } else {
          builder.append(' ');
        }
        builder.append(it.value());
      }
      return builder.toString();
    }

    public boolean equals(Object o) {
      if (!(o instanceof IntStream)) {
        return false;
      }
      IntStream c = (IntStream) o;
      IntIterator it = intIterator();
      IntIterator jt = c.intIterator();
      while (it.isValid() && jt.isValid()) {
        if (it.value() != jt.value()) {
          return false;
        }
        it.advance();
        jt.advance();
      }
      return !it.isValid() && !jt.isValid();
    }

    public int hashCode() {
      int result = 0;
      for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
        result *= 31;
        result += it.value();
      }
      return result;
    }

  }

  static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private InputReader.SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int[] readIntArray(int size) {
      int[] array = new int[size];
      for (int i = 0; i < size; i++) {
        array[i] = readInt();
      }
      return array;
    }

    public int read() {
      if (numChars == -1) {
        throw new InputMismatchException();
      }
      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (numChars <= 0) {
          return -1;
        }
      }
      return buf[curChar++];
    }

    public int readInt() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);

    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
      writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void close() {
      writer.close();
    }

    public void print(int i) {
      writer.print(i);
    }

  }

  static interface IntCollection extends IntStream {
    public int size();

  }

  static interface IntList extends IntReversableCollection {
    public abstract int get(int index);

    public abstract void removeAt(int index);

    default public IntIterator intIterator() {
      return new IntIterator() {
        private int at;
        private boolean removed;

        public int value() {
          if (removed) {
            throw new IllegalStateException();
          }
          return get(at);
        }

        public boolean advance() {
          at++;
          removed = false;
          return isValid();
        }

        public boolean isValid() {
          return !removed && at < size();
        }

        public void remove() {
          removeAt(at);
          at--;
          removed = true;
        }
      };
    }

  }

  static interface IntIterator {
    public int value() throws NoSuchElementException;

    public boolean advance();

    public boolean isValid();

  }

  static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
    public IntIterator intIterator();

    default public Iterator<Integer> iterator() {
      return new Iterator<Integer>() {
        private IntIterator it = intIterator();

        public boolean hasNext() {
          return it.isValid();
        }

        public Integer next() {
          int result = it.value();
          it.advance();
          return result;
        }
      };
    }

    default public int compareTo(IntStream c) {
      IntIterator it = intIterator();
      IntIterator jt = c.intIterator();
      while (it.isValid() && jt.isValid()) {
        int i = it.value();
        int j = jt.value();
        if (i < j) {
          return -1;
        } else if (i > j) {
          return 1;
        }
        it.advance();
        jt.advance();
      }
      if (it.isValid()) {
        return 1;
      }
      if (jt.isValid()) {
        return -1;
      }
      return 0;
    }

    default public int max() {
      int result = Integer.MIN_VALUE;
      for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
        int current = it.value();
        if (current > result) {
          result = current;
        }
      }
      return result;
    }

  }
}