#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int a, b, c;
int power(int x, int w) {
	if(x == 1) {
		return w;
	}
	if(x == 0) {
		return 1;
	}
	int p = power(x / 2, w);
	if(x % 2 == 0) {
		return (p * p) % mod;
	}
	return ((p * p) % mod * w) % mod;
}
signed main() {
	freopen("gcmod.in", "r", stdin);
	freopen("gcmod.out", "w", stdout);
	int t;
	cin >> t;
	for(int tt = 1; tt <= t; tt ++) {
		cin >> a >> b >> c;
		int x = abs(a - b);
		if(x == 1) {
			cout << x << endl;
			continue;
		}
		if(a == b) {
			a = power(c, a);
			b = power(c, b);
			cout << (a + b) % mod << endl;
			continue;
		}
		if(a > 10 && b > 10 && c > 10) {
			cout << __gcd(a - b, a + b) << endl;
			continue;
		} 
		a = power(c, a);
		b = power(c, b);
		cout << __gcd(a + b, x) % mod << endl;
	}
	return 0;
}