Determine K-Array Values

An array A consisting only of positive integers is called a K-array if every contiguous subarray of length K can be partitioned into two nonempty groups whose sums are equal. In other words, for every contiguous subarray B of length K, there exists a subset of indices, which is neither empty nor the full set, such that the sum of the corresponding elements equals \(\frac{\sum B}{2}\). Note that the total sum of the subarray must be even to allow such a partition.

For example, consider the array \(A = \{1, 2, 1, 3\}\). It is a 3-array because:

• The subarray \(\{1,2,1\}\) has a total sum of 4, and it can be partitioned into \(\{1,1\}\) and \(\{2\}\), both summing to 2.
• The subarray \(\{2,1,3\}\) has a total sum of 6, and it can be partitioned into \(\{1,2\}\) and \(\{3\}\), both summing to 3.

However, \(A\) is not a 2-array because the subarray \(\{1,2\}\) (with sum 3 which is odd) cannot be partitioned into two parts with equal sum.

Given T arrays, each containing only positive integers, determine all values of K for which the array is a K-array.

inputFormat

The first line contains an integer T, the number of test cases.

For each test case, the first line contains an integer n, the number of elements in the array. The second line contains n positive integers representing the elements of the array.

It is guaranteed that all numbers are positive integers.

outputFormat

For each test case, output all valid values of K (separated by a single space) for which the array is a K-array. If no valid K exists, output an empty line.

sample

3
4
1 2 1 3
3
2 2 2
5
1 1 1 1 1

3
2
2 4