Cho dãy số nguyên dương ~a_1, a_2, \dots, a_N~, mọi số trong dãy đều có không quá ~7~ ước nguyên dương.

Yêu cầu: Bỏ đi nhiều nhất (không được bỏ cả dãy) các phần tử trong dãy đã cho, sao cho tích các phần tử còn lại là một số chính phương. Nếu chỉ còn một phần tử thì tích các phần tử còn lại bằng chính số đó.

Input

• Dòng thứ nhất chứa một số nguyên dương ~N~ (~N \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ (~a_i \le 10^6~ với ~i=1 \dots N~).

Output

• Ghi ra một số nguyên dương duy nhất là số lượng nhiều nhất các phần tử có thể bỏ đi theo yêu cầu trên. Nếu không tồn tại cách loại bỏ nào thỏa mãn thì in ra ~-1~.

Sample Input 1

4
2 3 6 6

Sample Output 1

2