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ự 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ủ tất cả 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 một hàng ngang, sao cho thứ tự các tấm thẻ tăng dần từ trái qua 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 < |j - i| \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 chứa duy nhất số nguyên dương ~n~ ~(1 < n \le 10^5)~;

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

Output

Ghi ra một số nguyên dương duy nhất thỏa mãn yêu cầu bài toán.

Scoring

Sample Input 1

7
2
6
2
31
22
11
26

Sample Output 1

5

Notes

Số lượng tấm thẻ được chọn nhiều nhất là: 5 (Theo thứ tự các vị trí là: 1, 2, 4, 5, 7).

• Với ~i = 1, j = 2~: ~|a_2 - a_1| = 4 = 2^2~ và ~0 < 2 - 1 \le 10~;

• Với ~i = 2, j = 4~: ~|a_4 - a_2| = 25 = 5^2~ và ~0 < 4 - 2 \le 10~;

• Với ~i = 4, j = 5~: ~|a_5 - a_4| = 9 = 3^2~ và ~0 < 5 - 4 \le 10~;

• Với ~i = 5, j = 7~: ~|a_7 - a_5| = 4 = 2^2~ và ~0 < 7 - 5 \le 10~.