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

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$）.

Output

For each test case, output the maximum number.

2
3
1 1 1
4 
1 2 3 4

4
5

Hint

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