#866 OrBiTal (hard)

Statement

Statement language

$N$ orbitals are arranged in a circle and numbered $1$ through $N$ clockwise. Initially, the force intensity on every orbital is zero.

Placing a particle of strength $K$ on an orbital increases that orbital's intensity by $K$ . For every integer $t$ with $1\leq t\leq K-1$ , it also increases the intensities of the orbitals steps clockwise and counterclockwise by .

Thus, centered at the chosen orbital, one particle adds

1,2,\ldots,K-1,K,K-1,\ldots,2,1.

The orbitals are circular, so orbital $1$ follows orbital $N$ clockwise.

The integer strength $K$ must satisfy

1\leq K\leq\left\lfloor\frac{N+1}{2}\right\rfloor.

After choosing one value of $K$ , you may place any nonnegative number of particles of that strength. Each particle may be placed on any orbital, multiple particles may share an orbital, and all contributions accumulate.

The required final intensities $A_1,A_2,\ldots,A_N$ are given. Find every strength for which the required intensities can be obtained exactly.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, let $M$ be the number of valid strengths.

If at least one valid strength exists, print $M,K_1,K_2,\ldots,K_M$ on one line, where .

Constraints

$1\leq T\leq200\,000$ .
$1\leq N\leq200\,000$ .
$0 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	12	$A_i\leq3$ .
2	34	$A_1,\ldots,A_N$ form an arithmetic progression.

Samples

Input

Output