Cho ~n~ và dãy số nguyên ~a1, a2, ..., an~. Với mỗi ~i (1..n)~ hãy cho biết số lượng ước số nguyên tố số của ~ai~.

Input

• Dòng ~1~: số nguyên dương ~n (n \le 10^6)~
• Dòng ~2~: ghi ~n~ số nguyên dương ~ai (ai \leq 10^5)~

(các số trên ~1~ dòng được ghi cách nhau ~1~ dấu cách)

Output: Ghi trên ~n~ dòng

• Dòng i có dạng d: x y z ... (~d~ là số lượng ước số nguyên tố của ~ai~, x y z là danh sách các ước số nguyên tố của ~ai~ theo giá trị tăng dần (các số trên ~1~ dòng được ghi cách nhau ~1~ dấu cách))

Sample input

6
1 2 3 4 5 6

Sample output

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

Subtask

• ~50\%~ số test có ~n \le 10^3~

• ~50\%~ số test còn lại không có điều kiện gì thêm