Problem: Now you get Baby Ehab's first words: "Given an integer n, find the longest subsequence of [1,2, …, n-1] whose product is 1 modulo n." Please solve the problem.

A sequence b is a subsequence of an array a if b can be obtained from a by deleting some (possibly all) elements. The product of an empty subsequence is equal to 1.

Input

The only line contains the integer n (2 ≤ n ≤ 10^5).

Output

The first line should contain a single integer, the length of the longest subsequence.

The second line should contain the elements of the subsequence, in increasing order.

If there are multiple solutions, you can print any.

Examples

Input


5


Output


3
1 2 3 

Input


8


Output


4
1 3 5 7 

Note

In the first example, the product of the elements is 6 which is congruent to 1 modulo 5. The only longer subsequence is [1,2,3,4]. Its product is 24 which is congruent to 4 modulo 5. Hence, the answer is [1,2,3].

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class tr0 {
	static PrintWriter out;
	static StringBuilder sb;
	static long mod = (long) 1e9 + 7;
	static long inf = (long) 1e16;
	static int n, m, k;
	static ArrayList<Integer>[] ad;
	static int[][] remove, add;
	static long[][] memo, memo1[];
	static boolean vis[];
	static long[] inv, ncr[];
	static HashMap<Integer, Integer> hm;
	static int[] pre, suf, Smax[], Smin[];
	static int idmax, idmin;
	static ArrayList<Integer> av;
	static HashMap<Integer, Integer> mm;
	static boolean[] msks;
	static int[] lazy[], lazyCount;
	static int[] dist;
	static char[][] g;
	static int ave;
	static ArrayList<Integer> gl;
	static int[] a, q;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		int n = sc.nextInt();
		seive(1000001);
		long ans = 1;
		ArrayList<Integer> ar=new ArrayList<>();
		ar.add(1);
		for (int i = 2; i < n; i++) {
			x = 0;
			y = 0;
			d = 0;
			extendedEuclid(i, n);
			if (d != 1)
				continue;
			ans = (ans * i) % n;
			ar.add(i);
		}
		if(ans!=1) {
			for(int i=0;i<ar.size();i++)
				if(ar.get(i)==ans) {
					ar.remove(i);
					break;
				}
		}
		out.println(ar.size());
		for(int y:ar)
			out.print(y+" ");
		out.flush();
	}

	static int[] si;
	static ArrayList<Integer> primes;

	static void seive(int N) {
		si = new int[N];
		primes = new ArrayList<>();
		si[1] = 1;
		for (int i = 2; i < N; i++) {
			if (si[i] == 0) {
				si[i] = i;
				primes.add(i);
			}
			for (int j = 0; j < primes.size() && primes.get(j) <= si[i] && (i * primes.get(j)) < N; j++)
				si[primes.get(j) * i] = primes.get(j);
		}
	}

	static int x, y, d;

	static void extendedEuclid(int a, int b) {
		if (b == 0) {
			x = 1;
			y = 0;
			d = a;
			return;
		}
		extendedEuclid(b, a % b);
		int x1 = y;
		int y1 = x - a / b * y;
		x = x1;
		y = y1;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public int[] nextArrIntSorted(int n) throws IOException {
			int[] a = new int[n];
			Integer[] a1 = new Integer[n];
			for (int i = 0; i < n; i++)
				a1[i] = nextInt();
			Arrays.sort(a1);
			for (int i = 0; i < n; i++)
				a[i] = a1[i].intValue();
			return a;
		}

		public long[] nextArrLongSorted(int n) throws IOException {
			long[] a = new long[n];
			Long[] a1 = new Long[n];
			for (int i = 0; i < n; i++)
				a1[i] = nextLong();
			Arrays.sort(a1);
			for (int i = 0; i < n; i++)
				a[i] = a1[i].longValue();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}