H. Райан против Райанех
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Райан прилагает последние усилия, чтобы завоевать сердце Рейхане, утверждая, что он сильнее Райанех (то есть компьютера на персидском). Чтобы проверить это, Рейхане обращается за помощью к Хорезми. Хорезми объясняет, что множество является целочисленно линейно независимым, если ни один элемент в наборе не может быть получен как целочисленная линейная комбинация остальных. Райану задается набор целых чисел, и он должен найти одно из максимально возможных целочисленных линейно независимых подмножеств.

Обратите внимание, что один элемент всегда является целочисленным линейно независимым подмножеством.

Целочисленная линейная комбинация чисел $$$a_1, \ldots, a_k$$$ — это любая сумма вида $$$c_1 \cdot a_1 + c_2 \cdot a_2 + \ldots + c_k \cdot a_k$$$ где $$$c_1, c_2, \ldots, c_k$$$ — целые числа (которые могут быть нулевыми, положительными или отрицательными).

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — размер множества. Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^6$$$.

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

В первой строке каждого набора входных данных выведите размер наибольшего целочисленного линейно независимого подмножества.

В следующей строке выведите одно такое подмножество. Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
3
5
2 4 6 8 10
5
12 15 21 30 35
3
2 3 6
Выходные данные
2
4 6
3
35 21 30
2
2 3
Примечание

В 1 наборе входных данных: $$$\{4, 6\}$$$ — это целочисленное линейно независимое подмножество. Можно доказать, что не существует целочисленного линейно независимого подмножества, состоящего по крайней мере $$$3$$$ из элементов.

Во 2 наборе входных данных: $$$\{35, 21, 30\}$$$ — это целочисленное линейно независимое подмножество, поскольку никакая целочисленная линейная комбинация любых двух элементов не может создать третий. Не существует целочисленного линейно независимого подмножества, содержащего по крайней мере $$$4$$$ элемента.

В 3 наборе входных данных: $$$\{2, 3, 6\}$$$ не является целочисленным линейно независимым подмножеством, поскольку $$$6$$$ может быть записано как $$$6 \cdot 2 + (-2) \cdot 3$$$, что является целочисленной линейной комбинацией из $$$\{2, 3\}$$$.