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

Each test contains multiple test cases. The first line contains the number of test cases $T$ （$T \le 5$）.
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$）.

For each test case, output the maximum number.

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

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