Minh 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ừ 1 đến n, tấm thẻ thứ i ghi một số nguyên dương n. 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 \le i, j \le n)~ xếp cạnh nhau cần thỏa các điều kiện:

• ~0 < |i - j| \le 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 \le n \le 10^5)~
• Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương ai ~(1 \le a_i \le 10^9)~

Output

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

  Example

Input

7
2
6
2
31
22
11
26

Output

5

Note

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