#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
#define FastIO      ios_base::sync_with_stdio(false); cin.tie(0);
#define aPrint(a,b,c) for(int i=b;i<=c;i++){if(i>b)cout<<" ";cout<<a[i];}cout<<"\n";
#define vPrint(a)   for(int i=0;i<a.size();i++){cout<<a[i];if(i==a.size()-1)cout<<"\n";else cout<<" ";}
#define Case(t)     printf("Case %d: ", t)
#define clr(x,a)    memset(x,a,sizeof(x))
#define debug(x)   cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'
#define debug2(x,y) cerr<<__LINE__<<": "<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<'\n'
#define debug3(x,y,z) cerr <<__LINE__<<": "<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<"   "<<#z<<" = "<<z<<'\n'
#define debugW      cerr<<__LINE__<<": What?"<<'\n'

#define umap        unordered_map
#define plll        pair<ll, pair<ll, ll> >
#define pll         pair<ll, ll>
#define ff          first
#define ss          second
#define mp          make_pair
#define pb          push_back
#define ppb         pop_back
#define sf          scanf
#define pf          printf
#define eps         1e-9
#define all(a)      a.begin(),a.end()
#define allr(a)     a.rbegin(),a.rend()
#define Unique(a)   sort(all(a)), a.erase(unique(all(a)),a.end())

int dx[] = {+1, -1, +0, +0};
int dy[] = {+0, +0, +1, -1};
int KingX[] = {+0, +0, +1, -1, -1, +1, -1, +1};    // King's Move
int KingY[] = {-1, +1, +0, +0, +1, +1, -1, -1};    // King's Move
int KnightX[] = {-2, -2, -1, -1,  1,  1,  2,  2};  // Knight's Move
int KnightY[] = {-1,  1, -2,  2, -2,  2, -1,  1};  // Knight's Move

//inline int turnOn(int mask, int pos){return mask | (1<<pos);}
//inline int turnOff(int mask, int pos){return mask & ~(1<<pos);}
//inline bool isOn(int mask, int pos){return (bool)(mask&(1<<pos));}

template <class T> inline T bigmod(T b,T p,T M){T ret=1;for(;p>0;p>>=1){if(p&1) ret=(ret*b)%M;b=(b*b)%M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T lcm(T a,T b){return a*b / gcd<T>(a, b);}
template <class T> inline T power(T b,T p){ull x=1;while(p--)x*=b;return x;}
//const int mod = 1000000000 + 7;
const int mod = 998244353;
#define MAX 50000
#define pi        acos(-1.0)//3.1415926535897932
#define inf       1e9 + 7
/// 'N'+'A'+'E'+'E'+'E'+'M' ///

int main()
{
    FastIO;
    #ifndef ONLINE_JUDGE
        clock_t tStart = clock();
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif

    ll n; cin >> n;
    umap<ll, ll> vis;
    ll pro = 1;
    for(ll i = 1; i <= n - 1; i++) {
        if(gcd<ll>(i, n) == 1LL) {
            vis[i] = true;
            pro *= i;
            pro = pro % n;
        }
    }
    if(pro != 1) vis[pro] = false;

    vector<ll> ans;
    for(ll i = 1; i <= n - 1; i++) {
        if(vis[i]) ans.pb(i);
    }
    cout << ans.size() << "\n";
    vPrint(ans);

    #ifndef ONLINE_JUDGE
        printf("\n**Time -> %.10fs\n", (double)(clock()-tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

### Prompt

Please formulate a cpp solution to the following 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].

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
#define FastIO      ios_base::sync_with_stdio(false); cin.tie(0);
#define aPrint(a,b,c) for(int i=b;i<=c;i++){if(i>b)cout<<" ";cout<<a[i];}cout<<"\n";
#define vPrint(a)   for(int i=0;i<a.size();i++){cout<<a[i];if(i==a.size()-1)cout<<"\n";else cout<<" ";}
#define Case(t)     printf("Case %d: ", t)
#define clr(x,a)    memset(x,a,sizeof(x))
#define debug(x)   cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'
#define debug2(x,y) cerr<<__LINE__<<": "<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<'\n'
#define debug3(x,y,z) cerr <<__LINE__<<": "<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<"   "<<#z<<" = "<<z<<'\n'
#define debugW      cerr<<__LINE__<<": What?"<<'\n'

#define umap        unordered_map
#define plll        pair<ll, pair<ll, ll> >
#define pll         pair<ll, ll>
#define ff          first
#define ss          second
#define mp          make_pair
#define pb          push_back
#define ppb         pop_back
#define sf          scanf
#define pf          printf
#define eps         1e-9
#define all(a)      a.begin(),a.end()
#define allr(a)     a.rbegin(),a.rend()
#define Unique(a)   sort(all(a)), a.erase(unique(all(a)),a.end())

int dx[] = {+1, -1, +0, +0};
int dy[] = {+0, +0, +1, -1};
int KingX[] = {+0, +0, +1, -1, -1, +1, -1, +1};    // King's Move
int KingY[] = {-1, +1, +0, +0, +1, +1, -1, -1};    // King's Move
int KnightX[] = {-2, -2, -1, -1,  1,  1,  2,  2};  // Knight's Move
int KnightY[] = {-1,  1, -2,  2, -2,  2, -1,  1};  // Knight's Move

//inline int turnOn(int mask, int pos){return mask | (1<<pos);}
//inline int turnOff(int mask, int pos){return mask & ~(1<<pos);}
//inline bool isOn(int mask, int pos){return (bool)(mask&(1<<pos));}

template <class T> inline T bigmod(T b,T p,T M){T ret=1;for(;p>0;p>>=1){if(p&1) ret=(ret*b)%M;b=(b*b)%M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T lcm(T a,T b){return a*b / gcd<T>(a, b);}
template <class T> inline T power(T b,T p){ull x=1;while(p--)x*=b;return x;}
//const int mod = 1000000000 + 7;
const int mod = 998244353;
#define MAX 50000
#define pi        acos(-1.0)//3.1415926535897932
#define inf       1e9 + 7
/// 'N'+'A'+'E'+'E'+'E'+'M' ///

int main()
{
    FastIO;
    #ifndef ONLINE_JUDGE
        clock_t tStart = clock();
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif

    ll n; cin >> n;
    umap<ll, ll> vis;
    ll pro = 1;
    for(ll i = 1; i <= n - 1; i++) {
        if(gcd<ll>(i, n) == 1LL) {
            vis[i] = true;
            pro *= i;
            pro = pro % n;
        }
    }
    if(pro != 1) vis[pro] = false;

    vector<ll> ans;
    for(ll i = 1; i <= n - 1; i++) {
        if(vis[i]) ans.pb(i);
    }
    cout << ans.size() << "\n";
    vPrint(ans);

    #ifndef ONLINE_JUDGE
        printf("\n**Time -> %.10fs\n", (double)(clock()-tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

```