Residue Sequence Selection

Cho một số nguyên $n$. Hãy tìm dãy con dài nhất của dãy $[1, 2, ..., n - 1]$ sao cho tích của tất cả các phần tử trong dãy con đó chia cho $n$ có số dư là $1$.

Một dãy $b$ được gọi là dãy con của dãy $a$ nếu $b$ có thể thu được từ $a$ bằng cách xóa đi một số phần tử (có thể xóa tất cả hoặc không xóa phần tử nào). Tích của một dãy con rỗng được quy ước bằng $1$.

Dữ liệu vào

Dòng duy nhất chứa số nguyên $n$ ($2 ≤ n ≤ 10^5$).

Kết quả

Dòng đầu tiên in ra một số nguyên duy nhất là độ dài của dãy con dài nhất.

Dòng thứ hai in ra các phần tử của dãy con đó theo thứ tự tăng dần.

Nếu có nhiều phương án thỏa mãn, có thể in ra bất kỳ phương án nào.

Chấm điểm

Subtask 1 (30 points). $n ≤ 20$

Subtask 2 (70 points). $2 ≤ n ≤ 10^5$

Ví dụ

Input

5

Output

3
1 2 3

Ghi chú

Trong ví dụ đầu tiên, tích của các phần tử là $6$, chia cho $5$ có số dư là $1$. Dãy con duy nhất dài hơn là $[1, 2, 3, 4]$, có tích bằng $24$, chia cho $5$ có số dư là $4$. Do đó, đáp án là $[1, 2, 3]$.