Smallest Sum Perfect Square Subarray

You are given an array of positive integers. Your task is to find the smallest possible sum of a contiguous subarray such that the product of its elements is a perfect square.

A number x is a perfect square if and only if there exists an integer k such that \(x = k^2\). In other words, if \(\sqrt{x}\) is also an integer, then \(x\) is a perfect square.

If no contiguous subarray meets the condition, output -1.

The input consists of multiple test cases. For each test case, you will first be given an integer n representing the number of elements in the array, followed by n integers.

For each test case, print the answer on a new line.

inputFormat

The input is read from standard input and is in the following format:

T
n1
array[0] array[1] ... array[n1-1]
n2
array[0] array[1] ... array[n2-1]
...
nT
array[0] array[1] ... array[nT-1]

Where T is the number of test cases.

outputFormat

For each test case, output a single line containing the smallest sum of a contiguous subarray whose product is a perfect square. If no such subarray exists, output -1.

## sample

4
5
2 4 3 9 6
4
1 7 1 2
4
3 7 5 11
3
1 4 9

4
1
-1
1

</p>