Little Lidia likes playing with numbers. Today she has a positive integer n, and she wants to decompose it to the product of positive integers.
Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to n. She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.
Write a program that finds all decompositions, which little Lidia can play with today.
Input
The only line of the input contains a single integer n (1 ≤ n ≤ 10
18).
Output
In first line output the number of decompositions of n, or −1 if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number ki of elements in decomposition. Then print ki integers in this decomposition in any order. Don’t forget that decompositions which are different only in order of elements are considered the same.
| Input |
Output |
| 12 |
3
1 12
3 2 3 2
2 4 3 |
| 1 |
-1 |
In the second example 1 can be represented as product of any number of ones.