CF2258E.DivMEX

You are given an array $a_1, a_2, \ldots, a_n$ of positive integers.

Let $f(l,r)$ for $1 \leq l \leq r \leq n$ be the smallest positive integer that doesn't divide $\operatorname{lcm}(a_l, a_{l+1}, \ldots, a_r)$. Here, $\operatorname{lcm}$ of an array of integers denotes the least common multiple (LCM) of these integers.

Determine every positive integer $x$ such that there exists a pair of integers $(l,r)$ such that $1 \leq l \leq r \leq n$ and $f(l,r) = x$.

给你一个由正整数构成的数组 $a_1, a_2, \ldots, a_n$。

对任意满足 $1 \leq l \leq r \leq n$ 的整数对 $(l,r)$，定义 $f(l,r)$ 为不能整除 $\operatorname{lcm}(a_l, a_{l+1}, \ldots, a_r)$ 的最小正整数。其中，$\operatorname{lcm}$ 表示该整数数组的最小公倍数（LCM）。

请确定所有满足如下条件的正整数 $x$：存在整数对 $(l,r)$，使得 $1 \leq l \leq r \leq n$ 且 $f(l,r) = x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains $n$ ($1 \le n \le 2 \cdot 10^5$), denoting the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output two lines.

The first line should contain a single integer $k$ — the number of suitable integers $x$.

The second line should contain $k$ integers $x_1 \lt x_2 \lt \ldots \lt x_k$, the suitable integers in increasing order.

对于每个测试用例，输出两行。

第一行应包含一个整数 $k$ —— 满足条件的整数 $x$ 的个数。

第二行应包含 $k$ 个整数 $x_1 \lt x_2 \lt \ldots \lt x_k$，即按升序排列的所有满足条件的整数。

In the first test case, the only $(l,r)$ pair is $(1,1)$, and $f(1,1) = 2$.

In the second test case, $(l,r)=(1,1)$ yields the set of divisors ${ 1,2 }$, $(l,r)=(1,2)$ yields the set of divisors ${ 1, 2, 3, 6}$, and $(l,r)=(2,2)$ yields the set of divisors ${ 1, 3 }$. This means $f(1,1)=3$, $f(1,2)=4$, and $f(2,2)=2$. Since no other $(l,r)$ pair produces a different $f$ value, the answer is $[2,3,4]$.

For the last test case, $f(2,2)=2$, $f(1,1)=3$, and $f(1,5)=5$. It can be seen that no other values can be obtained.

在第一个测试用例中，唯一的 $(l,r)$ 对是 $(1,1)$，且 $f(1,1) = 2$。

在第二个测试用例中，$(l,r)=(1,1)$ 得到的约数集合为 $\{ 1,2 \}$，$(l,r)=(1,2)$ 得到的约数集合为 $\{ 1, 2, 3, 6\}$，而 $(l,r)=(2,2)$ 得到的约数集合为 $\{ 1, 3 \}$。这意味着 $f(1,1)=3$，$f(1,2)=4$，且 $f(2,2)=2$。由于不存在其他 $(l,r)$ 对能产生不同的 $f$ 值，答案为 $[2,3,4]$。

在最后一个测试用例中，$f(2,2)=2$，$f(1,1)=3$，且 $f(1,5)=5$。可以验证无法得到其他取值。