Nam và Hà

Ở trường THCS Yên Lạc Nam và Hà là 2 cặp đôi lớp 8A2 và nhân ngày lễ tình nhân sắp đến với và Nam muốn tặng Hà một số trang sức.

Anh mua n món trang sức. Các i mảnh -thứ có giá tương đương với i  + 1 , có nghĩa là, giá của các đồ trang sức là 2, 3, 4, ... n  + 1 .

Long đã đưa ra cho Nam một thách thức để tô màu những món đồ trang sức này sao cho hai món đồ không có màu giống nhau nếu giá của một món đồ là một ước nguyên tố của giá của món đồ kia. Ngoài ra, Long yêu cầu anh ta giảm thiểu số lượng màu sắc khác nhau được sử dụng.

Giúp Nam hoàn thành nhiệm vụ tầm thường này.

Input

Dòng duy nhất chứa số nguyên n duy nhất ( 1 ≤  n  100000 ) - số lượng đồ trang sức.

Output

Dòng đầu ra đầu tiên phải chứa một số nguyên k duy nhất , số lượng màu tối thiểu có thể được sử dụng để tô màu cho các mảnh trang sức với các ràng buộc nhất định.

Dòng tiếp theo nên bao gồm n số nguyên được phân tách bằng dấu cách (giữa 1 và k ) chỉ định màu của mỗi phần theo thứ tự tăng giá.

Nếu có nhiều cách để tô màu các mảnh bằng k màu, bạn có thể xuất bất kỳ màu nào trong số chúng.

Ví dụ

Input

3

Output

2
1 1 2

Input

4

Output

2
2 1 1 2

Ghi chú

Trong đầu vào đầu tiên, màu sắc cho các mảnh trang sức thứ nhất, thứ hai và thứ ba có giá tương ứng là 2 , 3 và 4 tương ứng là 1 , 1 và 2 .Trong trường hợp này, vì 2 là ước số nguyên tố của 4 , màu sắc của trang sức có giá 2 và 4 phải khác biệt.