Cho dãy gồm ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~. Bạn có quyền thay đổi các phần tử của dãy số này sao cho ~\forall i~ ~(1 \le i < n)~ ~LCM(a_i, a_{i+1})~ là các số chính phương.

Tại mỗi bước thay đổi, bạn chọn một vị trí ~i~ bất kì (~1 \leq i \leq n~) và cập nhật ~a_i~ := ~a_i \times x~ với ~x~ là một số nguyên dương bất kì. Không giới hạn số lần thay đổi của một phần tử.

Hãy tính số lần thay đổi tối thiểu để thỏa mãn yêu cầu đề bài.

Input

• Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

• Gồm một số nguyên không âm duy nhất là kết quả của đề bài.

Scoring

• Subtask ~1~ (~30~ điểm): ~n \le 1000~, ~a_i \le 5~ ~\forall~ ~1 \le i \le n~.

• Subtask ~2~ (~70~ điểm): Không có điều kiện gì thêm.

Sample Input 1

4
6 4 2 3

Sample Output 1

2

Sample Input 2

4
4 1 2 3

Sample Output 2

1

Notes

Ta có thể thay đổi dãy thành ~[162, 4, 2, 36]~ sau khi thay đổi phần tử đầu tiên và phần tử cuối cùng.