Mình là một học sinh rất yêu thích lập trình, em đã tạo ra một Game X nhằm giúp người chơi phát triển tư duy toán học.

Game được mô tả như sau: cho trước ~n~ tấm thẻ hình chữ nhật được đánh số thứ tự từ 1 đến ~n~, tấm thẻ thứ ~i~ ghi một số nguyên dương ~a_i~. Mỗi lượt chơi, người chơi cần chọn số lượng tấm thẻ nhiều nhất có thể và tuân thủ các quy tắc của trò chơi như sau:

Chọn ra một số tấm thẻ xếp thành hàng ngang, sao cho thứ tự tấm thẻ tăng dần theo chỉ số từ trái sang phải.

Tấm thẻ ~i, j~ ~(1 \leq i, j \leq n)~ xếp cạnh nhau cần thỏa các điều kiện:

• ~0 < |i - j| \leq 10~
• ~|a_j - a_i| > 0~
• ~|a_j - a_i|~ là bình phương của một số tự nhiên

Yêu cầu: Cho biết số lượng tấm thẻ nhiều nhất mà người chơi có thể chọn được trong mỗi lượt chơi.

Input

Dòng thứ nhất gồm ~n~ ~(1 \leq n \leq 10^5)~.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa số nguyên dương ~a_i~ ~(1 \leq a_i \leq 10^9)~.

Output

Gồm một dòng duy nhất là đáp án cần tìm.

Sample Test

Input

7
2
6
2
31
22
11
26

Output

5

Giải thích

Dãy dài nhất có ~5~ phần tử là: ~2, 6, 31, 32, 26~