Cho một dãy gồm hợp số . Bạn cần tô màu mỗi số bằng một trong màu (từ 1 đến ) sao cho hai điều kiện sau được thỏa mãn:
- Với mỗi màu từ 1 đến , có ít nhất một số được tô bằng màu đó.
- Với hai số bất kỳ và được tô cùng màu, thì ước chung lớn nhất của chúng lớn hơn 1 ().
Yêu cầu: Bạn hãy tìm một cách tô màu hợp lệ sử dụng số lượng màu nhỏ nhất có thể.
Dữ liệu:
- Dòng đầu tiên chứa số lượng bộ test .
- Mỗi bộ test bắt đầu bằng một số nguyên .
- Dòng tiếp theo chứa hợp số .
Kết quả: Với mỗi bộ test:
- Dòng đầu tiên in ra số màu tối thiểu được sử dụng.
- Dòng thứ hai in ra số nguyên, là màu của các số .
Ví dụ:
Dữ liệu:
Kết quả:
Giải thích: . Tất cả các cặp đều có GCD > 1, nên có thể tô cùng 1 màu.
Giới hạn:
- Tổng trên tất cả các test không vượt quá .
