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:
/**
 * Created by Himanshu
 **/

import java.util.*;
import java.io.*;
import java.math.*;

public class C1514 {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        Reader s = new Reader();
        int n = s.i();
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        list1.add(1);
        list2.add(1);
        for (int i = 2; i < n ; i++) {
            int x = gcd(n, i);
            if (x == 1) {
                long y = ((long) (i)) * i;
                if (y % n != 1) list1.add(i);
                else list2.add(i);
            }
        }
        boolean val1 = fun(list1,n);
        boolean val2 = fun(list2,n);
        if (val1 && val2) {
            int i=1 , j = 0;
            out.println(list1.size()+list2.size()-1);
            while (i < list1.size() && j < list2.size()) {
                int x = list1.get(i);
                int y = list2.get(j);
                if (x < y) {
                    out.print(x + " ");
                    i++;
                } else {
                    out.print(y + " ");
                    j++;
                }
            }
            while (i < list1.size()) {
                int x = list1.get(i);
                out.print(x + " ");
                i++;
            }
            while (j < list2.size()) {
                int y = list2.get(j);
                out.print(y + " ");
                j++;
            }
        } else if (val1) {
            int i=0;
            out.println(list1.size());
            while (i < list1.size()) {
                int x = list1.get(i);
                out.print(x + " ");
                i++;
            }
        } else if (val2) {
            int j=0;
            out.println(list2.size());
            while (j < list2.size()) {
                int y = list2.get(j);
                out.print(y + " ");
                j++;
            }
        } else {
            out.println(1);
            out.println(1);
        }
//        if (list1.size() > list2.size()) {
//
//            if (val == 1) {
//                out.println(list1.size());
//                for (int x : list1) out.print(x + " ");
//            } else {
//                val = 1;
//                for (int x : list2) val = (val*x)%n;
//                if (val == 1) {
//                    out.println(list2.size());
//                    for (int x : list2) out.print(x + " ");
//                } else {
//                    out.println(1);
//                    out.println(1);
//                }
//            }
//        } else {
//            long val = 1;
//            for (int x : list2) val = (val*x)%n;
//            if (val == 1) {
//                out.println(list2.size());
//                for (int x : list2) out.print(x + " ");
//            } else {
//                val = 1;
//                for (int x : list1) val = (val*x)%n;
//                if (val == 1) {
//                    out.println(list1.size());
//                    for (int x : list1) out.print(x + " ");
//                } else {
//                    out.println(1);
//                    out.println(1);
//                }
//            }
//        }
        out.flush();
    }
    private static boolean fun(ArrayList<Integer> list , int n) {
        long val = 1;
        for (int x : list) val = (val*x)%n;
        return val == 1;
    }
    public static void shuffle(long[] arr) {
        int n = arr.length;
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            long temp = arr[i];
            int randomPos = i + rand.nextInt(n - i);
            arr[i] = arr[randomPos];
            arr[randomPos] = temp;
        }
    }

    private static int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b,a%b);
    }

    public static long nCr(long[] fact, long[] inv, int n, int r, long mod) {
        if (n < r)
            return 0;
        return ((fact[n] * inv[n - r]) % mod * inv[r]) % mod;
    }

    private static void factorials(long[] fact, long[] inv, long mod, int n) {
        fact[0] = 1;
        inv[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = (fact[i - 1] * i) % mod;
            inv[i] = power(fact[i], mod - 2, mod);
        }
    }

    private static long power(long a, long n, long p) {
        long result = 1;
        while (n > 0) {
            if (n % 2 == 0) {
                a = (a * a) % p;
                n /= 2;
            } else {
                result = (result * a) % p;
                n--;
            }
        }
        return result;
    }

    private static long power(long a, long n) {
        long result = 1;
        while (n > 0) {
            if (n % 2 == 0) {
                a = (a * a);
                n /= 2;
            } else {
                result = (result * a);
                n--;
            }
        }
        return result;
    }

    private static long query(long[] tree, int in, int start, int end, int l, int r) {
        if (start >= l && r >= end) return tree[in];
        if (end < l || start > r) return 0;
        int mid = (start + end) / 2;
        long x = query(tree, 2 * in, start, mid, l, r);
        long y = query(tree, 2 * in + 1, mid + 1, end, l, r);
        return x + y;
    }

    private static void update(int[] arr, long[] tree, int in, int start, int end, int idx, int val) {
        if (start == end) {
            tree[in] = val;
            arr[idx] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx > mid) update(arr, tree, 2 * in + 1, mid + 1, end, idx, val);
        else update(arr, tree, 2 * in, start, mid, idx, val);
        tree[in] = tree[2 * in] + tree[2 * in + 1];
    }

    private static void build(int[] arr, long[] tree, int in, int start, int end) {
        if (start == end) {
            tree[in] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, tree, 2 * in, start, mid);
        build(arr, tree, 2 * in + 1, mid + 1, end);
        tree[in] = (tree[2 * in + 1] + tree[2 * in]);
    }

    static class Reader {
        private InputStream mIs;
        private byte[] buf = new byte[1024];
        private int curChar, numChars;

        public Reader() {
            this(System.in);
        }

        public Reader(InputStream is) {
            mIs = is;
        }

        public int read() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = mIs.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String s() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long l() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int i() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double d() throws IOException {
            return Double.parseDouble(s());
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int[] arr(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = i();
            }
            return ret;
        }

        public long[] arrLong(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = l();
            }
            return ret;
        }
    }
//    static class pairLong implements Comparator<pairLong> {
//        long first, second;
//
//        pairLong() {
//        }
//
//        pairLong(long first, long second) {
//            this.first = first;
//            this.second = second;
//        }
//
//        @Override
//        public int compare(pairLong p1, pairLong p2) {
//            if (p1.first == p2.first) {
//                if(p1.second > p2.second) return 1;
//                else return -1;
//            }
//            if(p1.first > p2.first) return 1;
//            else return -1;
//        }
//    }
//    static class pair implements Comparator<pair> {
//        int first, second;
//
//        pair() {
//        }
//
//        pair(int first, int second) {
//            this.first = first;
//            this.second = second;
//        }
//
//        @Override
//        public int compare(pair p1, pair p2) {
//            if (p1.first == p2.first) return p1.second - p2.second;
//            return p1.first - p2.first;
//        }
//    }
}