E. DivMEX
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Пусть $$$f(l,r)$$$ для $$$1 \leq l \leq r \leq n$$$ — минимальное целое положительное число, которое не делит $$$\operatorname{lcm}(a_l, a_{l+1}, \ldots, a_r)$$$. Здесь $$$\operatorname{lcm}$$$ массива целых чисел обозначает наименьшее общее кратное (НОК) этих чисел.

Определите все целые положительные числа $$$x$$$, для которых существует пара целых чисел $$$(l,r)$$$ такая, что $$$1 \leq l \leq r \leq n$$$ и $$$f(l,r) = x$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите две строки.

В первой строке должно содержаться одно целое число $$$k$$$ — количество подходящих чисел $$$x$$$.

Во второй строке должны содержаться $$$k$$$ целых чисел $$$x_1 \lt x_2 \lt \ldots \lt x_k$$$ — подходящие числа в порядке возрастания.

Пример
Входные данные
3
1
1
3
2 3 1
5
4 3 1 3 4
Выходные данные
1
2 
3
2 3 4 
3
2 3 5
Примечание

В первом наборе входных данных единственная пара $$$(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$$$. Можно показать, что никакие другие значения получить невозможно.