题目：https://codeforces.com/problemset/problem/1748/D
当时自己做的时候完全没什么想法，可能一个原因就是当时总想找充要条件
首先题解说了一个很显然的性质，即\((a,b,d)\)和\((2a,2b,2d)\)是同解的（如果不考虑x的限制），所以首先可以把\((a,b,d)\)都尽可能多地除掉\(2^k\)，这样至少有一个数是奇数（保证了\(a,b,d\geq 1\)所以自然不可能除到0）
这样：
- 如果d是偶数，则\(a,b\)至少一者为奇数，而奇数按位或之后还是奇数，d|奇数必然不可能
- 所以d只能是奇数，否则无解，那么此时如何找一组解应该是本题第二个可能卡住的地方
- 不过这毕竟只要找到一组解，那就干脆放宽条件，因为位运算是很麻烦的！！
- 所以干脆直接把a，b有数字的那些位置都填上1,
- 因为k一定是不超过30的，假如我对于30到k位都填上1，也就是移动了k位之后，从最低到30-k位填1，剩下的部分是\(2^{30-k}p\)，则要有\(2^k(2^{30-k}p+2^{30-k}-1)\equiv 0(\bmod 2^k d')\)，则\(p\equiv (\frac{1}{2})^{30-k}-1\equiv (\frac{d'+1}{2})^{30-k}-1(\bmod d')\)
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
ll ksm(ll a,ll b,ll MOD){
ll ret=1;
for(;b;b>>=1,a=a*a%MOD)if(b&1)ret=ret*a%MOD;
return ret;
}
ll solve(){
ll a,b,d,p;
cin>>a>>b>>d;
a|=b;
int k=0;
while(!(a&1)&&!(d&1)){
a>>=1;d>>=1;
k++;
}
if(!(d&1))return -1;
p=(ksm((d+1)/2,30-k,d)+d-1)%d;
ll ans=((p<<(30-k))+(1ll<<(30-k))-1)<<k;
return ans;
}
int main(){
fastio;
int T;cin>>T;
while(T--)cout<<solve()<<endl;
return 0;
}