题目描述
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
输入格式
见题面
输出格式
见题面
样例输入
20200920
样例输出
1100144