Antichain
View as PDFGiven a positive integer ~n~. Let ~S~ be the set of all positive divisors of ~n~.
Partition the set ~S~ into subsets such that:
every element of ~S~ belongs to exactly one subset;
no two subsets contain the same element;
for every pair of elements ~x, y~ in the same subset, either ~x|y~ or ~y|x~.
Find the minimum number of subsets needed and one valid partition.
Input
The first line contains an integer ~t~ ~(1 \leq t \leq 10)~, the number of test cases.
Each test case consists of one line containing an integer ~n~ ~(1 \leq n \leq 10^{18})~.
Output
For each test case:
The first line contains an integer ~k~, the minimum possible number of subsets.
Each of the next ~k~ lines has the form ~m, a_1, a_2, \dots, a_m~, representing a subset consisting of the elements ~a_1, a_2, \ldots, a_m~.
Scoring
| Subtask | Score | Constraints |
|---|---|---|
| 1 | ~500~ | ~n \leq 1000~ |
| 2 | ~1000~ | ~n \leq 10^{12}~ |
| 3 | ~2000~ | No additional constraints |
| Total | ~3500~ |
Sample Input 1
3
6
60
36
Sample Output 1
2
3 1 3 6
1 2
4
5 1 5 15 30 60
3 3 6 12
3 2 10 20
1 4
3
5 1 3 9 18 36
3 2 6 12
1 4
Comments