Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Ehab's REAL Number Theory Problem

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 \le n \le 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2020 06:23:36 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|