Partitions

Brian has found the Legendary Set of Numbers, a fabled set of positive integers said to have mysterious properties. Being a very kind person, he decides to share the set with his two closest friends, Abhilash and Kevin. He has known them for a long time, and they squabble at the least provocation, so he needs to split the set in an equitable way.

Abhilash loves the LCM, or least common multiple. The LCM of a set is the smallest positive integer divisible by all of its elements. Kevin loves the GCD, or greatest common divisor. The GCD of a set is the largest positive integer that divides all of its elements.

Brian wants to partition the set into two parts such that the LCM of the part given to Abhilash equals the GCD of the part given to Kevin. He quickly finds such a partition in the Legendary Set of Numbers. Playing around more, he realizes there are exactly $42$ ways to do so!

Brian thinks this is no coincidence, since this is the Legendary Set of Numbers. He wonders whether it is the smallest set with exactly $42$ partitions where the LCM of one part is the GCD of the other. He also asks about other counts. Specifically, what is the smallest $n$ such that some set of $n$ distinct positive integers can be partitioned in exactly $k$ ways where the LCM of one part is the GCD of the other?

Brian also asks you to supply such a set as proof. Since the numbers may get large, give each one as its prime factorization, with the numbers in sorted increasing order.

A partition of a set $S$ is a pair of nonempty sets $A$ and $B$ with $A \subset S$, $B \subset S$, $A \cup B = S$, and $A \cap B = \emptyset$. For $k = 1$, the smallest set is $\{1, 4, 5\}$. Its only partition is $\{1\}$ and $\{4, 5\}$, where the LCM of $\{1\}$ and the GCD of $\{4, 5\}$ are both $1$.

The input is a single line containing one integer $k$ ($1 \leq k \leq 10^4$).

Output one line with the integer $n$, the smallest size of a set as described above.

Then output $n$ lines. The $i$th line describes the $i$th smallest number in the set. Each line has the form $f\ p_1\ q_1\ p_2\ q_2\ \dots\ p_f\ q_f$, where adjacent numbers are separated by a space. Here $f$ is the number of distinct prime factors of the number, and for $1 \leq i \leq f$, $p_i$ is a prime factor and $q_i$ is its multiplicity. The values must satisfy $0 \leq f \leq 10^3$, $2 \leq p_i \leq 2 \cdot 10^3$, and $1 \leq q_i \leq 10^5$.