Giải mã

Cho một hợp số $n$. Ta viết tất cả các ước của $n$ lớn hơn $1$ lên một vòng tròn, mỗi ước đúng một lần. Thứ tự ban đầu của các ước trên vòng tròn là do ta tự chọn.

Mỗi bước, ta được chọn hai số kề nhau trên vòng tròn và chèn BCNN (bội chung nhỏ nhất) của chúng vào giữa hai số đó. Số vừa chèn trở thành một phần tử của vòng tròn và tham gia vào quan hệ kề như mọi số khác. Ta có thể lặp lại thao tác này bao nhiêu lần tùy ý.

Vòng tròn được gọi là đã giải mã nếu mọi cặp số kề nhau đều không nguyên tố cùng nhau.

Hãy chọn thứ tự ban đầu sao cho số bước cần thực hiện là ít nhất, và cho biết số bước ít nhất đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số lượng bộ dữ liệu.
• Mỗi dòng trong $t$ dòng tiếp theo chứa một hợp số $n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai dòng:

• Dòng thứ nhất: thứ tự ban đầu của các ước lớn hơn $1$ trên vòng tròn (phần tử cuối cùng được coi là kề với phần tử đầu tiên).
• Dòng thứ hai: số bước ít nhất cần thực hiện với thứ tự đó.

Nếu có nhiều thứ tự cùng cho số bước ít nhất, in ra thứ tự bất kỳ.

Ràng buộc

• $1\le t\le 100$
• $4\le n\le {10}^9$, $n$ là hợp số
• Tổng số ước của $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$

Ví dụ