Cho một đồ thị gồm ~N~ đỉnh, mỗi đỉnh có trọng số nguyên dương ~a_i~. ~(a_i, a_j)~ là cạnh của đồ thị khi vào chỉ khi ~gcd(a_i, a_j) > 1~. Đề bài cho 2 đỉnh ~s, t~ (với trọng số tương ứng là ~a_s~ và ~a_t~), bạn cần tìm và in ra số lượng đỉnh trên đường đi ngắn nhất từ ~s~ tới ~t~.

Input

• Dòng đầu chứa ~2 \le N \le 3 \times 10^5~, số lượng đỉnh.
• Dòng tiếp theo chứa ~N~ số ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 3 \times 10^5)~.

Output

• Nếu không có đường đi ghi ra ~-1~. Ngược lại, in ra đường đi ngắn nhất.

Sample Input 1

7
7 14 9 6 8 15 31
5 6

Sample Output 1

3

Sample Input 2

7
7 14 9 6 8 15 31
5 5

Sample Output 2

1

Sample Input 3

7
7 14 9 6 8 15 31
5 7

Sample Output 3

-1

Subtask

• 25% số điểm có ~N \le 100~;
• 25% số điểm có ~N \le 1000~;
• 50% số điểm không có ràng buộc gì thêm.