Một tập các số được gọi là đẹp nếu không tồn tại một tập con nào của tập đó có tích là số chính phương. Cho dãy ~A~ có ~n~ số tự nhiên, hãy tìm tập con đẹp có nhiều phân từ nhất của ~A~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ ~(n \leqslant 1000)~.
• Dòng sau chứa ~n~ số tự nhiên của dãy ~A~ ~(1 \leqslant A_i \leqslant 1000)~.

OUTPUT

• Một số nguyên duy nhất là số lượng phần từ lớn nhất của tập con.

SAMPLE TEST

Input:

5
8 2 1 6 7 

Output:

3