解题思路

给定互不相同的正整数数组 a1…an，要把所有元素分到两个非空数组 b 与 c 中，使得： 对 b 的任意非空子序列 d 与 c 的任意非空子序列 e，d 中所有元素的乘积都不是e 中所有元素的乘积的整数倍。

关键观察

若存在某个素数 p，使得 c 中的每个数都含有素因子 p，而 b 中的所有数都不含素因子 p，则任取 d ⊆ b、e ⊆ c：

• e 的乘积一定含有素因子 p；

题目内容

给定一个长度为 $n$ 的数组 {$a_1,a_2,…,a_n$}(元素互不相同)。你需要将所有元素分到两个最初为空的数组 $b$ 与 $c$ 中，使得：

• 数组 $b$ 与 $c$ 均为非空数组；

• 对于数组 $b$ 的任意非空子序列 $d=${$d_i,…,d_x$} 与数组 $c$ 的仼意非空子序列 $e =${$e_1,…, e_y$}，都有 $\prod_{i=1}^{x} d_{i}$ 不是 $\prod_{j=1}^{y} e_{j}$ 整数倍。

请输出任意一组满足条件的数组 $b$ 与 $c$ ，可以证明在题目限制中恒有解。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦ T ≦ 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(2 ≦n ≦2×10^5)$，表示数组长度;

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦ a_i≦ 10^6)$ ，表示数组元素，题目保证数组中元素互不相同。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 × 10^5$ 。

输出描述

对于每一组测试数据，依次输出四行：

• 第一行输出一个整数，表示数组 $b$ 的长度;

• 第二行输出该长度个整数，表示数组 $b$ 的元素;

• 第三行输出一个整数，表示数组 $c$ 的长度;

• 第四行输出该长度个整数，表示数组 $0$ 的元素。

若存在多种合法划分，输出任意一种即可。若存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。

样例1

输入

2
4
2 3 1 4
6
2 3 4 9 25

输出

2
1 3
2
2 4
3
3 9 25
2
2 4