Cho một số nguyên dương ~N~ ~(1 ≤ N ≤ 10⁶)~.

Với mỗi số nguyên từ 1 đến ~N~, ta xét tất cả các ước số của nó (bao gồm cả 1 và chính nó).

Yêu cầu: Hãy đếm xem, với mỗi số từ 1 đến ~N~, số đó xuất hiện bao nhiêu lần trong vai trò là ước số của các số từ 1 đến ~N~.

Input

Một dòng duy nhất chứa số nguyên dương ~N~.

Output

Gồm ~N~ dòng. Dòng thứ i in ra theo định dạng:

i: X

Trong đó:

i là số từ 1 đến N.

X là số lần số i xuất hiện làm ước số của các số từ 1 đến N.

Ví dụ

Input:

5

Output:

1: 5  
2: 2  
3: 1  
4: 1  
5: 1