Dung và Nhật Huy đang chuẩn bị mở cho mình một quán bán trà sữa với món kinh doanh bán chạy nhất là trà sữa kem trứng dừa nướng full topping. Với mong muốn quán trở nên đông khách, cô ấy đã bảo Nhật Huy đi mua ~n~ chú mèo dễ thương và đã nhờ Nhật Huy gắn lên con mèo thứ ~i~ một màn hình LED chứa số ~a_i~ và đồng thời chuẩn bị một trò chơi lập trình vào ngày khai trương, khi anh ấy sắp xếp ~n~ con mèo thành một hàng và mỗi khách hàng có một lượt để tìm dãy mèo ma thuật.

Dãy mèo ma thuật là một dãy liên tiếp chứa những con mèo, và sau khi tính tích các số xuất hiện ở màn hình LED, thì số vừa tính ra là một số chính phương. Phần thưởng của trò chơi là ~D~ ly trà sữa với ~D~ là độ dài tìm được.

Yêu cầu: Hãy tìm phần thưởng lớn nhất mà một người chơi có thể nhận được. Nói cách khác, hãy tìm dãy con liên tiếp có độ dài dài nhất, mà tích các phần tử của dãy là số chính phương.

INPUT: Đọc từ file văn bản MEOW.INP:

Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 3 \times 10^5~) là số phần tử của dãy.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6 + 3~) là các phần tử của dãy.

OUTPUT: Xuất ra file văn bản MEOW.OUT:

Giá trị ~D~ tìm được.

SAMPLE INPUT 1

3
2 8 5

SAMPLE OUTPUT 1

2

Dãy dài nhất thỏa mãn là ~2, 8~.

SAMPLE INPUT 2

5
7 7 8 2 99

SAMPLE OUTPUT 2

4

Dãy dài nhất thỏa mãn là ~7, 7, 8, 2~.

SUBTASKS