Cho số nguyên dương \(N\). Tính các giá trị \(\varphi(1), \varphi(2), \dots, \varphi(N)\).

Định dạng đầu vào

• Một dòng chứa số nguyên \(N\) (\(1 \le N \le 10^6\)).

Định dạng đầu ra

• In ra \(N\) số nguyên \(\varphi(1), \varphi(2), \dots, \varphi(N)\), cách nhau bởi dấu cách.

Ví dụ

Input:

6

Output:

1 1 2 2 4 2

Ràng buộc

• 100% số điểm: \(N \le 10^6\).