Cho \(N\). Tính mảng \(\mu(n)\) và \(\varphi(n)\) cho tất cả \(n \le N\) dùng sàng tuyến tính.

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

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

Định dạng đầu ra

• \(N\) dòng, dòng thứ \(i\) in \(\mu(i)\) và \(\varphi(i)\).

Ví dụ

Input:

6

Output:

1 1
-1 1
-1 2
0 2
-1 4
1 2

Ràng buộc

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