问题 F: Perfect square number

You have an array of $n$ elements a1,,a2, $...$ , an.

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 1, a2, ..., an（1≤ai≤300）.

2
3
1 1 1
4 
1 2 3 4

4
5