Chữ ký thừa số của mã dữ liệu

Bối cảnh và bài toán

Một hệ thống phát hiện lỗi lưu "chữ ký số học" của mỗi mã dữ liệu dưới dạng các thừa số nguyên tố và số mũ tương ứng. Để xử lý hàng loạt bản ghi, hệ thống cần tạo chữ ký cho nhiều số trong cùng một phiên.

Chữ ký phải được chuẩn hóa theo thứ tự prime tăng dần để hai hệ thống có thể so sánh trực tiếp.

Yêu cầu

Phân tích mỗi x thành các lũy thừa nguyên tố. In số lượng prime khác nhau và các cặp prime exponent theo prime tăng dần.

Input

• Dòng 1: số nguyên q.
• q dòng tiếp theo: mỗi dòng chứa x.

Output

Với mỗi x, in k p1 e1 p2 e2 ... pk ek, trong đó k là số prime khác nhau và p1 < p2 < ... < pk. Nếu x=1, in 0.

Ràng buộc

• 1 <= q <= 2 * 10^5
• 1 <= x <= 10^6

Chấm điểm

Ví dụ 1

Input

3
1
12
360

Output

0
2 2 2 3 1
3 2 3 3 2 5 1

Giải thích. 12=2^2*3; 360=2^3*3^2*5. Số 1 không có thừa số nguyên tố nên chữ ký bắt đầu bằng 0.

Ví dụ 2

Input

2
17
100

Output

1 17 1
2 2 2 5 2

Giải thích. 17 là nguyên tố. 100=2^2*5^2.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.