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>
using namespace std;

#define ll long long
vector < ll > val; long long N;
void euclid(ll a , ll b , ll &x , ll &y){!b ? (x = 1 , y = 0) : (euclid(b , a % b , y , x) , y -= a / b * x);}

int main(){
	cin >> N; N *= 2; ll ans = 2 * N;
	for(int i = 2 ; 1ll * i * i <= N ; ++i)
		if(N % i == 0){ll pw = 1; while(N % i == 0){N /= i; pw *= i;} val.push_back(pw);}
	if(N != 1) val.push_back(N);
	for(int i = 1 ; i < 1 << val.size() ; ++i){
		ll p1 = 1 , p2 = 1; for(int j = 0 ; j < val.size() ; ++j) (i >> j & 1 ? p1 : p2) *= val[j];
		ll x , y; euclid(p1 , p2 , x , y); if(x <= 0) x += p2;
		ans = min(ans , p1 * x - 1);
	}
	cout << ans; return 0;
}
