G. Wael-utiful Array
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Wael is known for his Telegram bio "We Travel Across the Horizons of Beauty", which actually reflects the problems he comes up with. They are always about maximizing, , you guessed it, the Beauty, or as he calls it, the Wael-uty.

Wael defines the Wael-uty of two unordered integers $$$(X,$$$ $$$Y)$$$ as the number of pairs of integers $$$(i, j)$$$ such that:

  • $$$1 \le i \le X$$$.
  • $$$1 \le j \le Y$$$.
  • $$$(i + j)$$$ is a perfect square

Well, according to Wael, Wael-uty is not only about pairs, it can also be found within arrays. Wael defines an array $$$B$$$ of length $$$M$$$ to be Wael-utiful if it holds that for any index $$$i$$$ such that $$$1 \le i \lt M$$$:

  • $$$(B_i + B_{i + 1})$$$ is a perfect square.

You will be given an array $$$A$$$ of length $$$N$$$. You need to find a Wael-utiful subset $$$B$$$ of elements of $$$A$$$ such that the sum of Wael-uty of each two adjacent elements is maximum possible.

A perfect square is a positive integer that is obtained by multiplying an integer by itself, i.e. $$$4$$$ is a perfect square because it is obtained from $$$2 \times 2$$$, but $$$6$$$ is not.

Note that:

  • an array $$$U$$$ is said to be a subset of array $$$V$$$, if $$$U$$$ can be obtained from $$$V$$$ by deletion of several (possibly zero or all) elements.
  • the elements of any chosen subset must be taken in their original order in array $$$A$$$.
Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 2 \cdot 10^4)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains a single integer $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ — the length of the array $$$A$$$.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le 10^5)$$$ — the values in array $$$A$$$.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$

Output

For each testcase print a single integer — the maximum possible sum of Wael-uty of a Wael-utiful subset $$$B$$$ of $$$A$$$.

Example
Input
4
6
4 12 3 4 12 3
6
4 25 11 25 11 3
3
1 2 3
3
1 7 4
Output
24
102
1
0