An và Bình chơi một trò chơi với số nguyên \(N\). Mỗi lượt, người chơi chọn một ước số nguyên tố \(p\) của số hiện tại, rồi thay số đó bằng \text{số hiện tại} - p. Người nào đến lượt mình mà không thể chọn được ước số nguyên tố nào (số hiện tại < 2) sẽ thua. Cả hai đều chơi tối ưu.

Hãy xác định người thắng cuộc.

Đị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

• In ra \(1\) nếu An (người đi trước) thắng, \(2\) nếu Bình thắng.

Ví dụ

Input:

5

Output:

1

Ràng buộc