#include <bits/stdc++.h>
using namespace std;
int t, a, b, n, mod = 1000000007;
unsigned long long A;
unsigned long long ans = 0;

unsigned long long power(int a, int x) {
	if (x == 0)
		return 1;
	if (x == 1)
		return a;
	if (x % 2 == 0)
		return power(a, x / 2) * power(a, x / 2);
	else
		return power(a, x - 1) * a;
}

unsigned long long gcd(int x, int y) {
	if (y == 0)
		return x;
	return gcd(y, x % y);
}

unsigned long long ab(int x) {
	if (x < 0)
		return -x;
	return x;
}

int main() {
	freopen("gcmod.in", "r", stdin);
	freopen("gcmod.out", "w", stdout);
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		cin >> a >> b >> n;
		A = power(a, n) + power(b, n);
		ans = gcd(A, ab(a - b)) % mod;
		cout << ans << endl;
	}
	return 0;
}