#include <bits/stdc++.h>
 
using i64 = long long;
 
const i64 MOD = 1e9 + 7;
 
std::map<int, int> mp;
 
i64 pmod(i64 n, i64 p) {
	i64 ret = 1;
	for (; p; p >>= 1, n = n * n % MOD) 
		if (p & 1) ret = ret * n % MOD;
	return ret;
}
 
void solve() {
	i64 a, b, n;
	std::cin >> a >> b >> n;
	i64 x = (pmod(a, n) % MOD + pmod(b, n) % MOD) % MOD, y = std::abs(a - b);
	mp.clear();
	for (int i = 2; i <= y / i; ++ i) {
		if (y % i == 0) {
			while (y % i == 0) y /= i;
			++ mp[i];
		}
		if (y != 1) 
			++ mp[y];
	}
	bool flag = true;
	i64 res = 1;
	while (flag) {
		flag = false;
		for (auto& [i, j] : mp)
			if (x % i == 0) 
				res = res * i, x /= i, -- j, flag = true;
			else 
				j = 0;
	}
	std::cout << res << '\n';
}
 
int main() {
	freopen("gcmod.in", "r", stdin); 
	freopen("gcmod.out", "w", stdout);
	i64 tt; std::cin >> tt;
	while (tt --) solve();
	return 0;
}