분할

Brian은 전설의 수 집합(Legendary Set of Numbers)을 찾았다. 신비로운 성질을 가진다고 알려진 양의 정수들의 집합이다. Brian은 매우 친절한 사람이라서 이 집합을 가장 가까운 친구 둘, Abhilash와 Kevin과 나누기로 했다. 두 친구는 사소한 자극에도 다투기 때문에, Brian은 집합을 공평하게 나눠야 한다.

Abhilash는 LCM, 즉 최소공배수를 좋아한다. 집합의 LCM은 모든 원소로 나누어떨어지는 가장 작은 양의 정수다. Kevin은 GCD, 즉 최대공약수를 좋아한다. 집합의 GCD는 모든 원소를 나누는 가장 큰 양의 정수다.

Brian은 집합을 두 부분으로 나눠서, Abhilash가 받는 부분의 LCM이 Kevin이 받는 부분의 GCD와 같아지게 하려 한다. 그는 전설의 수 집합에서 그런 분할을 곧바로 찾았다. 더 따져 보니 정확히 $42$가지 방법으로 나눌 수 있었다!

Brian은 이것이 우연이 아니라고 본다. 전설의 수 집합이기 때문이다. 그는 한 부분의 LCM이 다른 부분의 GCD가 되는 분할이 정확히 $42$가지인 집합 중 가장 작은 것이 이 집합인지 궁금해한다. 42 말고 다른 값에 대해서도 생각해 본다. 구체적으로, 서로 다른 양의 정수 $n$개로 이루어진 집합 중에서, 한 부분의 LCM이 다른 부분의 GCD가 되는 분할이 정확히 $k$가지인 집합이 존재하는 가장 작은 $n$은 얼마인가?

Brian은 이 답이 맞다는 것을 보이려고, 그런 집합의 예도 함께 제시해 달라고 한다. 수가 매우 커질 수 있으므로, 각 수는 소인수분해한 형태로 주고 오름차순으로 정렬한다.

집합 $S$의 분할이란, 공집합이 아닌 두 집합 $A$, $B$로서 $A \subset S$, $B \subset S$, $A \cup B = S$, $A \cap B = \emptyset$을 만족하는 쌍을 말한다. $k = 1$인 경우 가장 작은 집합은 $\{1, 4, 5\}$이다. 가능한 분할은 $\{1\}$과 $\{4, 5\}$ 하나뿐이고, $\{1\}$의 LCM과 $\{4, 5\}$의 GCD는 모두 1이다.

입력은 한 줄이며, 정수 $k$ ($1 \leq k \leq 10^4$) 하나가 주어진다.

한 줄에 위 조건을 만족하는 집합의 최소 크기 $n$을 출력한다.

이어서 $n$줄을 출력한다. $i$번째 줄은 집합에서 $i$번째로 작은 수를 나타낸다. 각 줄은 $f\ p_1\ q_1\ p_2\ q_2\ \dots\ p_f\ q_f$ 형식이며, 인접한 수는 공백으로 구분한다. 여기서 $f$는 그 수의 서로 다른 소인수 개수이고, $1 \leq i \leq f$에 대해 $p_i$는 소인수, $q_i$는 그 중복도다. 값은 $0 \leq f \leq 10^3$, $2 \leq p_i \leq 2 \cdot 10^3$, $1 \leq q_i \leq 10^5$를 만족해야 한다.