Problem Description

An array $A$ containing only positive integers is called a $K$ array if every consecutive subsequence of length $K$ can be split into two parts whose element sums are equal. For example, $\{1,2,1,3\}$ is a $3$ array, because $\{1,2,1\}$ can be split into $\{1,1\}$ and $\{2\}$ with both sums equal to $2$, and $\{2,1,3\}$ can be split into $\{1,2\}$ and $\{3\}$ with both sums equal to $3$. However, this array is not a $2$ array, because $\{1,2\}$ cannot be split into two parts with equal element sums.

Given $T$ arrays containing only positive integers, for each array, find all possible values of $K$ such that the array is a $K$ array.

Input Format

The first line contains an integer $T$.

Then $T$ arrays are described. For each array, the first line contains an integer $N$, and the second line contains $N$ integers representing the elements of the array.

Output Format

Output $T$ lines. For each line, first output the number of valid $K$ values, then output all valid $K$ values in increasing order.

2
7
7 3 5 1 3 3 5
6
1 2 3 5 8 3

2 4 6
2 3 6

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (10 pts): $1 \le N \le 30$.
• Subtask 2 (20 pts): $31 \le N \le 120$.
• Subtask 3 (70 pts): $121 \le N \le 1000$.

For $100\%$ of the testdata, $1 \le T \le 20$, and for each array, the sum of its elements does not exceed $10^5$.

Notes

This problem is translated from eJOI2021 Day 1 B Kpart.

Translated by ChatGPT 5