一开始还手动拓欧找规律，发现好像玩不了。
然后想了想，A-B这个数比较小，枚举它的因子判断合不合法就行了。
需要特判A=B的情况。
#include<cstdio>
#include<algorithm>
#define ll long long
#define ld long double
using namespace std; ll a,b,n,c,t,d,A,B;
int i;
const int MOD=1e9+;
inline void MM(ll &a,ll M){while(a>=M)a-=M;}
inline ll cc(ll x,ll y,ll M){
x=x*y-(ll)(((ld)x*y+0.01)/M)*M;
return x<?x+M:x;
}
inline ll mi(ll x,ll y,ll M){
ll ans=;
x%=M;
while(y){
if (y&) ans=cc(ans,x,M);
y>>=;x=cc(x,x,M);
}
return ans;
}
inline bool ju(ll x){
return (mi(a,n,x)+mi(b,n,x))%x==;
}
inline void work(){
scanf("%lld%lld%lld",&a,&b,&n);
c=a-b;
if (c==){
printf("%d\n",(mi(a,n,MOD)+mi(b,n,MOD))%MOD);
return;
}
for (i=;1LL*i*i<=c;i++)
if (c%i==&&ju(c/i)){
printf("%lld\n",c/i%MOD);
return;
}
for (i--;i;i--)
if (c%i==&&ju(i)){
printf("%lld\n",i%MOD);
return;
}
}
int main(){
scanf("%lld",&t);
while(t--) work();
}