Nhà thám hiểm H giải nghệ toán học, quyết định thực hiện chuyến du lịch vòng quanh n thành phố. Mỗi thành phố được đánh mã bằng một số nguyên dương a[i]. Là người yêu thích số học, ở mỗi thành phố, H đều phân tích mã số thành các thừa số nguyên tố, sau đó ghi lại tất cả các số mũ của các thừa số nguyên tố trong một cuốn sổ tay.

Sau khi kết thúc hành trình, H mở cuốn sổ và muốn bạn giúp anh ta sắp xếp lại tất cả các số mũ đó theo thứ tự các thành phố đi qua, sau đó in ra.

Tuy nhiên, do các thành phố quá nhiều, bạn phải xử lý bài toán thật nhanh!

🎯 Input Dòng đầu tiên là số nguyên ~n~ ~(1 ≤ n ≤ 10⁵)~ — số thành phố.

Dòng thứ hai gồm n số nguyên ~a[i]~ ~(1 ≤ a[i] ≤ 10⁶)~ — mã số của từng thành phố.

✅ Output In ra một dòng duy nhất gồm tất cả các số mũ thu được khi phân tích các số ~a[i]~, cách nhau bởi dấu cách.

🔎 Ví dụ

Input:

4
30 60 75 12

Output:

1 1 1 2 1 1 1 2 2 1

Giải thích

30 = 2^1 * 3^1 * 5^1 → số mũ: 1 1 1

60 = 2^2 * 3^1 * 5^1 → số mũ: 2 1 1

75 = 3^1 * 5^2 → số mũ: 1 2

12 = 2^2 * 3^1 → số mũ: 2 1 → Tổng hợp: 1 1 1 2 1 1 1 2 2 1