To read the problem statement in English, choose the language using the flag on the navigation bar.

Cho số ~n~. Hãy tìm dãy số nguyên dương ~a~ thỏa mãn các điều kiện sau:

1. Các phần tử của dãy ~a~ không quá ~n + 1~.

2. Không có hai phần tử trong dãy ~a~ có cùng giá trị.

3. Với mỗi ~x~ từ ~2~ đến ~n~, tồn tại cặp chỉ số ~(i, j)~ sao cho ~i \neq j~ và ~a_i \equiv a_j \pmod x~.

4. Số phần tử của dãy ~a~ là nhỏ nhất có thể.

Input

Gồm một số nguyên ~n~ (~2 \le n \le 10^5~).

Output

Dòng đầu tiên in ra ~k~ – độ dài dãy ~a~ tìm được.

Dòng thứ hai in ra ~k~ số nguyên ~a_1, a_2, \ldots, a_k~ thỏa mãn điều kiện đề bài.

Nếu có nhiều đáp án thỏa mãn điều kiện, hãy in ra đáp án bất kì.

Scoring

• Subtask 1, tương ứng với ~10~ số điểm, có ~n \le 16~.

• Subtask 2, tương ứng với ~90~ số điểm, không có giới hạn gì thêm

Tổng cộng bài toán có ~100~ điểm.

Sample Input 1

5

Sample Output 1

4
1 3 5 6

Notes

Có thể thấy dãy ~[1, 3, 5, 6]~ thỏa mãn điều kiện thứ nhất và thứ hai của đề bài. Dãy này cũng thỏa mãn điều kiện thứ ba:

• Cặp phần tử mang giá trị ~1~ và ~5~ có cùng số dư là ~1~ khi chia cho ~x = 2~.

• Cặp phần tử mang giá trị ~3~ và ~6~ cùng chia hết cho ~x = 3~.

• Cặp phần tử mang giá trị ~1~ và ~5~ có cùng số dư là ~1~ khi chia cho ~x = 4~.

• Cặp phần tử mang giá trị ~1~ và ~6~ có cùng số dư là ~1~ khi chia cho ~x = 5~.

Có thể chỉ ra rằng, với ~n = 5~ thì không có dãy ~a~ nào có ít hơn ~4~ phần tử thỏa yêu cầu đề bài.