Given an array $$$a$$$ of length $$$n$$$, containing integers. And there are two initially empty arrays $$$b$$$ and $$$c$$$. You need to add each element of array $$$a$$$ to exactly one of the arrays $$$b$$$ or $$$c$$$, in order to satisfy the following conditions:

Both arrays $$$b$$$ and $$$c$$$ are non-empty. More formally, let $$$l_b$$$ be the length of array $$$b$$$, and $$$l_c$$$ be the length of array $$$c$$$. Then $$$l_b, l_c \ge 1$$$.
For any two indices $$$i$$$ and $$$j$$$ ($$$1 \le i \le l_b, 1 \le j \le l_c$$$), $$$c_j$$$ is not a divisor of $$$b_i$$$.

Output the arrays $$$b$$$ and $$$c$$$ that can be obtained, or output $$$-1$$$ if they do not exist.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.

Output

For each test case, output a single integer $$$-1$$$ if a solution does not exist.

Otherwise, in the first line, output two integers $$$l_b$$$ and $$$l_c$$$ — the lengths of arrays $$$b$$$ and $$$c$$$ respectively.

In the second line, output $$$l_b$$$ integers $$$b_1, b_2, \ldots, b_{l_b}$$$ — the elements of array $$$b$$$.

In the third line, output $$$l_c$$$ integers $$$c_1, c_2, \ldots, c_{l_c}$$$ — the elements of array $$$c$$$.

If there are multiple solutions, output any of them. You can output the elements of the arrays in any order.

Note

In the first test case, a solution does not exist.

In the second test case, we can obtain $$$b = [1, 3, 5]$$$ and $$$c = [2, 4]$$$. Then elements $$$2$$$ and $$$4$$$ do not divide elements $$$1, 3$$$ and $$$5$$$.

In the fifth test case, we can obtain $$$b = [4, 8, 4]$$$ and $$$c = [12, 12]$$$.

United We Stand

Examples