|
F |
Integer
Grouping Input: Standard Input Output: Standard Output |
|
Given N distinct integers, A1, A2, ..., AN
you have to organize the integers into m
groups such that each integer is a member of exactly one group. And a group
should follow the following conditions:
1)
Each
group should contain at least two integers.
2)
If
a1 a2 ... ak
(a1 < a2 < ... < ak) are the integers
of a particular group then
a.
ai and ai+1 have to share a common
divisor greater than 1, for all i = 1
to k-1
b.
a1 ≤ M
c. ak ≥ M
where M is the median of the N integers (from A1, A2, ..., AN). Median of an N element array can be found by first sorting the array and then picking its middle element if N is odd and average of 2 middle elements if N is even.
Here we say m as the cardinality. You have to find two such group configurations - one with maximum cardinality and another with minimum cardinality.
Input
First line of input will be number of test cases, T (T ≤ 60).
Each test case will be described by 2 lines – first line will contain the integer N (1 ≤ N ≤ 200). The next line will contain N integers, Ai (2 ≤ Ai ≤ 109) separated by a single space.
Output
For each test case, you should start your output by “Case x:” where x is the test case number starting from 1. If it is impossible to find such grouping that complies with the above-mentioned conditions, you should output “Impossible” (without the quotes). Otherwise, you should output maximum (m1) and minimum (m2) cardinality of the groups in one line. In the next m1 lines, you should output the m1 groups for maximum cardinality and then in the next m2 lines, you should output the m2 groups for minimum cardinality. The numbers in each line should be in ascending order. However, the groups themselves can be outputted in any order. If there are many possible group configurations that yield maximal / minimal cardinality, output any of them.
Sample Input Output for Sample
Input
|
2 3 3 5 7 7 2 3 4 6 12 14 16 |
Case 1: Impossible Case 2: 3 2 2 14 16 3 12 4 6 2 4 6 3 12 14 16 |