Given is an integer N. Find the minimum possible positive integer k such that (1+2+\cdots+k) is a multiple of N. It can be proved that such a positive integer k always exists.

Constraints

* 1 \leq N \leq 10^{15}
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N


Output

Print the answer in a line.

Examples

Input

11


Output

10


Input

20200920


Output

1100144
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

ll mygcd(ll a,ll b){
    return a?mygcd(b%a,a):b;
}

ll INV(ll a, ll m) {
    ll m0 = m, y = 0, x = 1;
    if (m == 1)    return 0;
    while (a > 1) {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0) x += m0;
    return x;
}

int main()
{
    ll n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    if(n==1){
        cout<<1<<"\n";
        return 0;
    }

    n<<=1;

    ll res = n-1;

    ll curv;
    ll gc;

    for(ll i=2;i*i<=n;i++){
        if(n%i)continue;

        a = i;
        b = n/i;

        gc = mygcd(a,b);

        if(gc>1)continue;

        curv = INV(a,b);
        curv *= a;
        res = min(res,curv-1);

        curv = INV(b,a);
        curv *= b;
        res = min(res,curv-1);
    }

    cout<<res<<"\n";

    return 0;
}
