开始解决一下历史遗留问题，好像八九道题的样子，估计要补个不少时间的。
首先我们很容易发现 就是 找 最小的 x 使得 x(x+1)%(2n)==0
然后 x与x+1是互质的、
不妨令 x=ax,x+1=by,
就是找 by-ax=1
除此之外还要保证这个数能整除2n，所以我们暴力枚举n的每个质因子是给前面还是后面即可
注意当y等于一的时候，后面必须等于 y-1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll& d,ll& x,ll& y) {
if (!b) {
d = a;
x = 1;
y = 0;
} else {
exgcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
const int N = 1e6+5;
ll vis[N],b[N],ind=0;
void init(){
for(int i=2;i<N;i++){
if(vis[i])continue;
b[ind++]=i;
for(int j=i+i;j<N;j+=i){
vis[j]=1;
}
}
}
int t;ll n;
ll p[20],c[20],cnt=0;
int main(){
ios::sync_with_stdio(false);
init();
cin>>t;
while (t--){
cin>>n;cnt=0;
n*=2;
for(int i=0;i<ind&&b[i]*b[i]<=n;i++){
if(n%b[i]==0){
p[cnt]=1;
while (n%b[i]==0){
n/=b[i];
p[cnt]*=b[i];
}
cnt++;
}
}
ll a,b,d,x,y;
ll ans = 1e18;
if(n)p[cnt]=n,c[cnt]=1,cnt++;
for(int i=0;i<(1<<cnt);i++){
a=1,b=1;
for(int j=0;j<cnt;j++){
if(i>>j&1){
a*=p[j];
}else{
b*=p[j];
}
}
if(a==1){ans = min(ans,b-1);}
else {
exgcd(a,-b,d,x,y);
if(d==1) {
y = (y % a + a) % a;
ans = min(ans, y * b);
}
}
}
cout<<ans<<endl;
}
}