Perfect square number

Problem Description

You have an array of $n$ elements $a_1,$ $a_2,$ $...$ , $a_n$. You have an operation that can modify the value of a certain position to any of the values in $[1,300]$. (You can only perform it once) Find the maximum number of intervals that satisfy the interval sum is a Perfect square number.

Input

The description of the test cases follows. The first line contains one integer $n$（$1\le \ n \le 300$）. The second line contains $n$ integers $a_1, \ a_2, \ ..., \ a_n$（$1\le a_i \le 300$）.

Output

For each test case, output the maximum number.

Sample Input

3
1 1 1

Sample Output

4

Hint

For the first query, change $a_2=3$. For the second query, change $a_2=1$.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）