E. DivMEX
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.

Output

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.

Example
Input
3
1
1
3
2 3 1
5
4 3 1 3 4
Output
1
2 
3
2 3 4 
3
2 3 5
Note

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.