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 rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn 200000
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

vector<ll> fac;
ll ans;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) {x=1;y=0;return a;}
    ll G=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;y=tmp-a/b*y;
    return G;
}

void dfs(int dep,ll A,ll B)
{
    if(dep==-1)
    {
        ll x,y;
        exgcd(A,B,x,y);
        if(y>=0) x+=B,y-=A;
        ans=min(ans,-B*y);
        return;
    }
    dfs(dep-1,A*fac[dep],B);
    dfs(dep-1,A,B*fac[dep]);
}
int main()
{
    ll n; scanf("%lld",&n); n*=2;
    for(int i=2;1ll*i*i<=n;i++) if(n%i==0)
    {
        ll x=1;
        while(n%i==0) n/=i,x*=i;
        fac.pb(x);
    }
    if(n>1) fac.pb(n);
    ans=1ll<<60;
    int N=fac.size();
    dfs(N-1,1,1);
    printf("%lld\n",ans);
    return 0;
}