메타고니아의 정육면체 분배

메타고니아에는 귀족 가문이 100개 있다. 해마다 유일자의 예언자가 그 가운데 몇 가문에 의식용 정육면체를 나누어 준다. 유일자는 분배 규칙을 두 가지 정해 두었다.

• 어떤 가문이 정육면체를 하나 이상 받으면, 그 개수의 소인수는 2 또는 3뿐이다.
• 같은 해에 한 가문이 $a > 0$개, 다른 가문이 $b > 0$개를 받으면 $a$는 $b$로 나누어떨어지지 않고 $b$도 $a$로 나누어떨어지지 않는다.

당신은 유일자의 예언자다. 앞으로 $t$년 동안 해마다 나누어 줄 정육면체 개수를 미리 알고 있다. 해마다 그 해의 정육면체를 남김없이 나누어 주어야 한다.

첫 줄에 앞으로의 햇수 $t$가 주어진다 ($1 \le t \le 1000$). 이어지는 $t$개 줄에 $i$번째 해에 나누어 줄 정육면체 개수 $n_i$가 한 줄에 하나씩 주어진다 ($1 \le n_i \le 10^{18}$).

해마다 두 줄을 출력한다. 첫 줄에는 $i$번째 해에 정육면체를 하나 이상 받는 가문의 수 $m_i$를 출력한다 ($1 \le m_i \le 100$). 둘째 줄에는 각 가문이 받는 개수를 오름차순으로 공백으로 구분해 출력한다. 이 수의 합은 $n_i$와 같다.

규칙을 만족하는 분배가 여럿일 수 있으므로, 다음 절차로 만든 분배 하나만 정답으로 인정한다.

아직 나누어 주지 않은 개수를 $n$이라 하고, $n$이 0이 될 때까지 다음을 반복한다.

1. $n$을 나누어떨어지게 하는 가장 큰 2의 거듭제곱을 $2^a$라 하고, $q = n / 2^a$로 둔다. $q$는 홀수다.
2. $3^b \le q$를 만족하는 가장 큰 3의 거듭제곱을 $3^b$라 한다.
3. 한 가문에 $2^a \times 3^b$개를 준다.
4. $n$을 $n - 2^a \times 3^b$로 바꾼다.

이렇게 고른 개수를 오름차순으로 정렬해 출력한다. 이 절차는 항상 두 규칙을 만족하고 가문 수가 100을 넘지 않는다.