------Read problems statements in Hindi,
Mandarin chinese
, Russian and Vietnamese as well. ------ 

At ShareChat, there are are plenty of interesting problems to solve. Here is one of them.

Given integers $A$, $B$ and $N$, you should calculate the [GCD] of $A^{N} + B^{N}$ and $|A - B|$. (Assume that $GCD(0, a) = a$ for any positive integer $a$). Since this number could be very large, compute it modulo $1000000007$ ($10^{9} + 7$).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $A$, $B$ and $N$.

------  Output ------
For each test case, print a single line containing one integer — the required GCD modulo $10^{9} + 7$.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ A, B, N ≤ 10^{12}$
$B ≤ A$

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ A, B, N ≤ 10$

Subtask #2 (40 points): $1 ≤ A, B, N ≤ 10^{9}$

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------ 
2
10 1 1
9 1 5
----- Sample Output 1 ------ 
1
2
----- explanation 1 ------ 
Example case 1: $GCD(10^{1} + 1^{1}, 10 - 1) = GCD(11, 9) = 1$

Example case 2: $GCD(9^{5} + 1^{5}, 9 - 1) = GCD(59050, 8) = 2$

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math

def power(a, n, mod):
	res = 1
	while n > 0:
		if n & 1 == 1:
			res = res % mod * a % mod % mod
			n -= 1
		a = a % mod * a % mod % mod
		n = n // 2
	return res

def gcd(a, b, n, mod):
	if a == b:
		return (power(a, n, mod) + power(b, n, mod)) % mod
	possible = 1
	total = a - b
	for i in range(1, int(math.sqrt(total)) + 1):
		if total % i == 0:
			temp = (power(a, n, i) + power(b, n, i)) % i
			if temp == 0:
				possible = max(possible, i)
			temp = (power(a, n, total // i) + power(b, n, total // i)) % (total // i)
			if temp == 0:
				possible = max(possible, total // i)
	return possible % mod
case = int(input())
for _ in range(case):
	(a, b, n) = map(int, input().split(' '))
	mod = 1000000007
	res = gcd(a, b, n, mod)
	print(res)


from math import gcd
m = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print((pow(a, n, m) + pow(b, n, m)) % m)
		continue
	d = a - b
	print(gcd((pow(a, n, d) + pow(b, n, d)) % d, d) % m)


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(A, B, N) = list(map(int, input().split()))
	if A == B:
		print(pow(A, N, mod) + pow(B, N, mod))
		continue
	print(math.gcd(A - B, pow(A, N, A - B) + pow(B, N, A - B)))


from collections import defaultdict, Counter, deque
import math
import bisect
from itertools import accumulate
from math import ceil, log, gcd
from functools import lru_cache
from sys import stdin, stdout
import time
import atexit
import io
import sys
import string
import heapq

def primes(n):
	if n <= 2:
		return []
	sieve = [True] * (n + 1)
	for x in range(3, int(n ** 0.5) + 1, 2):
		for y in range(3, n // x + 1, 2):
			sieve[x * y] = False
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def write(*args, **kwargs):
	sep = kwargs.get('sep', ' ')
	end = kwargs.get('end', '\n')
	stdout.write(sep.join((str(a) for a in args)) + end)

def read():
	return stdin.readline().rstrip()

def primes_rwh(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def prime_factors(n):
	i = 2
	factors = []
	d = defaultdict(lambda : 0)
	for i in primes_rwh(int(n ** 0.5 + 1)):
		while n % i == 0:
			n //= i
			factors.append(i)
			d[i] += 1
	if n > 1:
		factors.append(n)
		d[n] += 1
	return (factors, d)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def lcm(x, y):
	lcm = x * y // math.gcd(x, y)
	return lcm
total = int(read())
for _ in range(total):
	(a, b, n) = [int(p) for p in read().split()]
	z = abs(a - b)
	g = 1
	if z == 0:
		print((a ** n + b ** n) % 1000000007)
		continue
	while z > 1 and n > 2:
		t = math.gcd(z, a * b)
		if t == 1:
			break
		g *= t
		g %= 1000000007
		n -= 2
		z //= t
	n = n % 2
	g *= math.gcd(z, a ** n + b ** n)
	g %= 1000000007
	print(g)


from math import *
from collections import *
from bisect import *
import heapq
import math
from itertools import permutations

def is_prime(n):
	for i in range(2, math.ceil(math.sqrt(n))):
		if n % i == 0:
			return False
	return True

def sieve(n):
	arr = [True for _ in range(n + 1)]
	for i in range(2, math.ceil(math.sqrt(n))):
		if arr[i] == True:
			for j in range(i * i, n + 1, i):
				arr[j] = False
	return arr

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def euclidean_distance(x1, y1, x2, y2):
	return sqrt(abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2)

def get_permutations(lo=0, hi=10):
	return list(permutations(range(lo, hi)))

def getDivisors(n):
	i = 1
	ans1 = []
	ans2 = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans1.append(i)
			else:
				ans1.append(i)
				ans2.append(n // i)
		i = i + 1
	return ans1 + ans2[::-1]

def solve():
	(a, b, n) = list(map(int, input().split()))

	def check(x, y):
		return x >= 0 and y >= 0 and (x < n) and (y < m)
	mod = int(1000000000.0 + 7)
	if a == b:
		x = power(a, n, mod)
		y = power(b, n, mod)
		z = int(x + y) % mod
		print(z)
	lis = getDivisors(a - b)
	for ele in lis[::-1]:
		if (power(a, n, ele) + power(b, n, ele)) % ele == 0:
			print(ele)
			return
n = 1
n = int(input())
while n:
	n -= 1
	solve()


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
t = ri()
mod = 1000000007

def power(a, b, mod):
	res = 1
	while b > 0:
		if b & 1:
			res *= a
			res %= mod
		a *= a
		a %= mod
		b >>= 1
	return res % mod
for test in range(t):
	(a, b, n) = rl()
	if a == b:
		print((power(a, n, mod) % mod + power(b, n, mod)) % mod)
	else:
		i = 1
		res = 1
		p = a - b
		while i * i <= p:
			if p % i == 0:
				tmp = (power(a, n, i) + power(b, n, i)) % i
				if tmp == 0:
					res = max(res, i)
				tmp = (power(a, n, p // i) + power(b, n, p // i)) % (p // i)
				if tmp == 0:
					res = max(res, p // i)
			i += 1
		print(res)


import sys
from collections import Counter, defaultdict, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return input()

def exp(a, n, inf):
	if n == 0:
		return 1
	t = exp(a, n // 2, inf)
	res = t * t
	if n % 2 == 1:
		res *= a
	return res % inf
for tastcas in range(int(input())):
	(a, b, n) = li()
	d = abs(a - b)
	inf = 1000000007
	if d == 0:
		print((exp(a, n, inf) + exp(b, n, inf)) % inf)
	else:
		print(gcd(d, (exp(a, n, d) + exp(b, n, d)) % d) % inf)


def modexp(X, n, mod):
	if n == 0:
		return 1
	temp = modexp(X, n // 2, mod)
	res = temp * temp
	if n % 2 == 1:
		res *= X
	return res % mod

def gcd(A, B):
	if B == 0:
		return A
	return gcd(B, A % B)
T = int(input())
for t in range(T):
	(A, B, N) = [int(i) for i in input().split()]
	diff = A - B
	res = 0
	if diff == 0:
		res = (modexp(A, N, 1000000007) + modexp(B, N, 1000000007)) % 1000000007
	else:
		res = gcd(diff, (modexp(A, N, diff) + modexp(B, N, diff)) % diff) % 1000000007
	print(res)


import math
t = int(input())
MOD = 1000000007

def exponential_mod(n, p, mod):
	if p == 0:
		return 1
	if p % 2 != 0:
		return exponential_mod(n, p - 1, mod) * n % mod
	tmp = exponential_mod(n, p // 2, mod) % mod
	return tmp * tmp % mod

def swap(a, b):
	tmp = a
	a = b
	b = tmp
while t > 0:
	t -= 1
	(a, b, n) = list(map(int, input().split()))
	if a == b:
		print((exponential_mod(a, n, MOD) + exponential_mod(b, n, MOD)) % MOD)
	else:
		if b > a:
			swap(a, b)
		print(int(math.gcd((exponential_mod(a, n, a - b) + exponential_mod(b, n, a - b)) % (a - b), a - b)))


n = int(input())
mod = 10 ** 9 + 7

def binary(base, power, mod):
	save = 1
	while power != 1:
		if power % 2 == 0:
			power = power // 2
			base = base * base % mod
		else:
			power = power - 1
			save = save * base % mod
	ans = save * base % mod
	return ans

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for i in range(n):
	(a, b, n) = list(map(int, input().split()))
	if b - a != 0:
		binary_solution = binary(a, n, max(a - b, b - a)) + binary(b, n, max(a - b, b - a))
		final_answer = gcd(binary_solution, max(a - b, b - a))
	else:
		binary_solution = binary(a, n, mod) + binary(b, n, mod)
		final_answer = gcd(binary_solution, max(a - b, b - a))
	print(final_answer)


from math import gcd

def power(x, y, m):
	if y == 0:
		return 1
	z = power(x, y // 2, m)
	if y % 2 == 1:
		return z * z % m * x % m
	else:
		return z * z % m
t = int(input())
MOD = 1000000007
for _ in range(t):
	(a, b, n) = [int(x) for x in input().split()]
	if abs(a - b) > 0:
		print(gcd(power(a, n, abs(a - b)) + power(b, n, abs(a - b)), abs(a - b)) % MOD)
	else:
		print((power(a, n, MOD) + power(b, n, MOD)) % MOD)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
x = int(input())
for i in range(x):
	(a, b, t) = map(int, input().split())
	if abs(a - b) > 0:
		print(gcd(pow(a, t, abs(a - b)) + pow(b, t, abs(a - b)), abs(a - b)) % (10 ** 9 + 7))
	else:
		print((pow(a, t) + pow(b, t)) % (10 ** 9 + 7))


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())
mod = 1000000007

def main():
	for _ in range(inp()):
		(a, b, n) = rv(int)
		if a == b:
			print(2 * pow(a, n, mod) % mod)
		else:
			x = abs(a - b)
			ans = (pow(a, n, x) + pow(b, n, x)) % x
			print(gcd(x, ans) % mod)
main()


mod_val = 10 ** 9 + 7

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def modexp(a, b, x):
	a %= x
	result = 1
	while b > 0:
		if b & 1:
			result = result * a % x
		a = a ** 2 % x
		b >>= 1
	return result

def solve(a, b, n):
	delta = a - b
	if delta == 0:
		return (modexp(a, n, mod_val) + modexp(b, n, mod_val)) % mod_val
	else:
		value = modexp(a, n, delta) + modexp(b, n, delta)
		value %= delta
		return gcd(delta, value) % mod_val
T = int(input())
for t in range(T):
	(a, b, n) = map(int, input().split(' '))
	print(solve(a, b, n))


def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def snek(a, b, m):
	a %= m
	ans = 1
	while b > 0:
		if b & 1 == 1:
			ans = ans * a % m
		a = a * a % m
		b >>= 1
	return ans % m
t = int(input())
m = 10 ** 9 + 7
for i in range(t):
	(a, b, n) = map(int, input().split())
	c = max(a, b) - min(a, b)
	ans = 0
	if c == 0:
		ans = (snek(a, n, m) + snek(b, n, m)) % m
	else:
		s = (snek(a, n, c) + snek(b, n, c)) % c
		ans = gcd(s, c) % m
	print(ans)


def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def power(a, b, m):
	a = a % m
	ans = 1
	while b > 0:
		if b & 1 == 1:
			ans = ans * a % m
		a = a * a % m
		b >>= 1
	return ans % m
t = int(input())
m = 10 ** 9 + 7
for ii in range(t):
	(a, b, n) = map(int, input().split())
	temp = max(a, b) - min(a, b)
	ans = 0
	if temp == 0:
		ans = (power(a, n, m) + power(b, n, m)) % m
	else:
		p = (power(a, n, temp) + power(b, n, temp)) % temp
		ans = gcd(p, temp) % m
	print(ans)


from math import gcd

def gcdd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def modexp(a, b, m):
	a = a % m
	ans = 1
	while b > 0:
		if b & 1 == 1:
			ans = ans * a % m
		a = a * a % m
		b >>= 1
	return ans % m
MOD = 1000000007
T = int(input())
for i in range(T):
	(A, B, N) = map(int, input().split())
	delta = A - B
	if delta == 0:
		print((modexp(A, N, MOD) + modexp(B, N, MOD)) % MOD)
	else:
		An_plus_Bn = modexp(A, N, delta) + modexp(B, N, delta)
		An_plus_Bn %= delta
		print(gcd(delta, An_plus_Bn) % MOD)


import itertools
import heapq
import collections
import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def inis():
	return input().split()

def stlt():
	return list(map(str, input().split()))

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	l = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			l.append(p)
	return l

def isPrime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False

def gcdofarray(a):
	x = 0
	for p in a:
		x = math.gcd(x, p)
	return x

def printDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	ans.sort()
	return ans

def CountDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	ans.sort()
	return len(ans)

def binaryToDecimal(n):
	return int(n, 2)

def countTriplets(a, n):
	s = set()
	for i in range(n):
		s.add(a[i])
	count = 0
	for i in range(n):
		for j in range(i + 1, n, 1):
			xr = a[i] ^ a[j]
			if xr in s and xr != a[i] and (xr != a[j]):
				count += 1
	return int(count // 3)

def generate_twin_prime(n):
	a = 0
	for i in range(1, n + 1):
		j = i + 2
		if isPrime(i) and isPrime(j):
			if 2 ^ (i ^ j) == 0:
				a += 1
	return a

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def countOdd(L, R):
	N = (R - L) // 2
	if R % 2 != 0 or L % 2 != 0:
		N += 1
	return N

def isPalindrome(s):
	return s == s[::-1]

def sufsum(test_list):
	test_list.reverse()
	res = [sum(test_list[:i + 1]) for i in range(len(test_list))]
	return res

def prsum(lst):
	return list(itertools.accumulate(lst))

def badachotabadachota(nums):
	nums.sort()
	i = 0
	j = len(nums) - 1
	ans = []
	cc = 0
	while len(ans) != len(nums):
		if cc % 2 == 0:
			ans.append(nums[j])
			j -= 1
		else:
			ans.append(nums[i])
			i += 1
		cc += 1
	return ans

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n / i
	if n > 2:
		ans.append(n)
	return ans

def closestMultiple(n, x):
	if x > n:
		return x
	z = int(x / 2)
	n = n + z
	n = n - n % x
	return n
for _ in range(inp()):
	(a, b, n) = invr()
	m = abs(a - b)
	if m == 0:
		m = int(1000000000.0 + 7)
	k1 = (pow(a, n, m) + pow(b, n, m)) % m
	if m == int(1000000000.0 + 7):
		print(k1 % int(1000000000.0 + 7))
	else:
		print(math.gcd(m, k1) % int(1000000000.0 + 7))


import math
mod = int(1000000000.0 + 7)
for i in range(int(input())):
	(a, b, n) = map(int, input().split())
	m = abs(a - b)
	if m == 0:
		m = mod
	k1 = (pow(a, n, m) + pow(b, n, m)) % m
	if m == mod:
		print(k1 % mod)
	else:
		print(math.gcd(m, k1) % mod)


m = 10 ** 9 + 7

def binpow(a, b, m):
	ans = 1
	a = a % m
	while b:
		if b & 1:
			ans = ans * a % m
			b -= 1
		else:
			a = a * a % m
			b >>= 1
	return ans
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print((binpow(a, n, m) + binpow(b, n, m)) % m)
		continue
	c = []
	r = abs(a - b)
	for i in range(1, int(r ** 0.5) + 1):
		if r % i == 0:
			c.append(i)
			if r // i != i:
				c.append(r // i)
	c.sort(reverse=True)
	for i in c:
		if (binpow(a, n, i) + binpow(b, n, i)) % i == 0:
			print(i)
			break


def modPower(a, n, mod):
	if n == 0:
		return 1
	if n == 1:
		return a
	l = modPower(a, int(n / 2), mod)
	if n % 2 == 0:
		return l % mod * l % mod % mod
	l = l % mod * l % mod % mod
	l = a % mod * l % mod
	return l

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def solve():
	inp = input()
	arr = [int(e) for e in inp.split(' ')]
	a = arr[0]
	b = arr[1]
	n = arr[2]
	diff = a - b
	mod = diff
	if diff == 0:
		mod = 1000000007
	g = modPower(a, n, mod) + modPower(b, n, mod)
	if diff != 0:
		g = gcd(diff, g)
	ans = g % 1000000007
	print(ans)
t = input()
t = int(t)
for k in range(t):
	solve()


from math import gcd
md = 10 ** 9 + 7
for t in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print((pow(a, n, md) + pow(b, n, md)) % md)
		continue
	d = a - b
	x = (pow(a, n, d) + pow(b, n, d)) % d
	print(gcd(x, d))


import math, sys, collections
from collections import defaultdict as dd, Counter as cc
input = sys.stdin.readline
istr = lambda : input().strip()
inum = lambda : int(input().strip())
imap = lambda : map(int, input().strip().split())
ilist = lambda : list(map(int, input().strip().split()))

def findmodpow(a, b, m=int(1000000000.0 + 7)):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res % m

def gcdsmall(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
try:
	n = int(input())
	while True:
		try:
			(a, b, n) = list(map(int, input().split()))
			mod = 1000000007
			diff = abs(a - b)
			if diff == 0:
				pow_a = findmodpow(a, n, mod)
				pow_b = findmodpow(b, n, mod)
				ans = (pow_a + pow_b) % mod
				print(ans)
			else:
				pow_a = findmodpow(a, n, diff)
				pow_b = findmodpow(b, n, diff)
				ans = gcdsmall((pow_a + pow_b) % diff, diff) % mod
				print(ans)
		except EOFError:
			print('Error: ', e)
			break
except Exception as e:
	pass


def power(x, y, p):
	if y == 0:
		return 1
	temp = power(x, y // 2, p)
	if y % 2 == 0:
		return temp * temp % p
	else:
		return x * (temp * temp) % p % p

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
testcases = int(input())
for t in range(testcases):
	(a, b, n) = list(map(int, input().split()))
	mod = 1000000007
	diff = abs(a - b)
	if diff == 0:
		pow_a = power(a, n, mod)
		pow_b = power(b, n, mod)
		ans = (pow_a + pow_b) % mod
		print(ans)
	else:
		pow_a = power(a, n, diff)
		pow_b = power(b, n, diff)
		ans = gcd((pow_a + pow_b) % diff, diff) % mod
		print(ans)


def power_cal(A, n, jump):
	res = 1
	base = A
	if n == 1:
		return A % jump
	while n > 0:
		if n % 2 == 0:
			n = n // 2
			base = base % jump * (base % jump) % jump
		else:
			n -= 1
			res = res % jump * (base % jump) % jump
	return res

def Check(A, B, N, big):
	A = power_cal(A, N, big)
	B = power_cal(B, N, big)
	if (A + B) % big == 0:
		return True
	return False

def find_all_divisors(A, B, N, jump):
	if jump == 0:
		return ((A % 1000000007) ** N + (B % 1000000007) ** N) % 1000000007
	candidate = 1
	for i in range(1, int(jump ** (1 / 2) + 1)):
		if jump % i == 0:
			big = jump // i
			if Check(A, B, N, i):
				candidate = max(candidate, i)
			if Check(A, B, N, big):
				candidate = max(candidate, big)
	return candidate
for _ in range(int(input())):
	(A, B, N) = list(map(int, input().split()))
	jump = max(A - B, B - A)
	my_gcd = find_all_divisors(A, B, N, jump)
	print(my_gcd % 1000000007)


import math
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b, n) = list(map(int, input().split()))
	n1 = a - b
	if n1 == 0:
		ans = pow(a, n, mod) + pow(b, n, mod)
		print(ans % mod)
	else:
		l = []
		for i in range(1, int(math.sqrt(n1) + 1)):
			if n1 % i == 0:
				l.append(i)
				l.append(n1 // i)
		ans = 0
		for i in range(len(l)):
			a1 = pow(a, n, l[i]) + pow(b, n, l[i])
			a1 = a1 % l[i]
			if a1 == 0:
				ans = max(ans, l[i])
		print(ans % mod)


mod = 10 ** 9 + 7
import sys
import math

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		(A, B, N) = map(int, sys.stdin.readline().split())
		if A == B:
			x = pow(A, N, mod)
			y = pow(B, N, mod)
			print((x + y) % mod)
		else:
			if A > B:
				x = A - B
			else:
				x = B - A
			a1 = pow(A, N, x)
			b1 = pow(B, N, x)
			print(math.gcd((a1 + b1) % x, x))
main()


import math
t = int(input())
for i in range(t):
	(a, b, n) = input().split()
	(a, b, n) = (int(a), int(b), int(n))
	m = 10 ** 9 + 7
	if a > b:
		p = a - b
	else:
		p = b - a
	if p == 0:
		x = pow(a, n, m)
		y = pow(b, n, m)
		print((x + y) % m)
	else:
		x = pow(a, n, p)
		y = pow(b, n, p)
		z = math.gcd(x + y, p)
		print(z % m)


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
import math
for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	if A == B:
		a = power(A, N, 1000000007)
		b = power(B, N, 1000000007)
		ans = a + b
		print(ans % 1000000007)
	else:
		a = power(A, N, A - B)
		b = power(B, N, A - B)
		ans = (a + b) % (A - B)
		print(math.gcd(ans, A - B))


mod = 1000000007

def power(a, n, d):
	res = 1
	while n:
		if n % 2:
			res = res % d * (a % d) % d
			n -= 1
		else:
			a = a % d * (a % d) % d
			n = n // 2
	return res

def gcd(a, b, n):
	if a == b:
		return (power(a, n, mod) + power(b, n, mod)) % mod
	can = 1
	num = a - b
	i = 1
	while i * i <= num:
		if num % i == 0:
			tmp = (power(a, n, i) + power(b, n, i)) % i
			if tmp == 0:
				can = max(can, i)
			tmp = (power(a, n, num // i) + power(b, n, num // i)) % (num // i)
			if tmp == 0:
				can = max(can, num // i)
		i += 1
	return can % mod
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split(' '))
	ans = gcd(a, b, n)
	print(ans)


import math
for _ in range(int(input())):
	mod = pow(10, 9) + 7
	(a, b, n) = map(int, input().split())
	if a == b:
		print((pow(a, n, mod) + pow(b, n, mod)) % mod)
	else:
		ans = math.gcd(pow(a, n, abs(a - b)) + pow(b, n, abs(a - b)), abs(a - b))
		print(ans % mod)


import math
mod = 1000000007

def gcc(a, b, n):
	if a == b:
		return pow(a, n, mod) + pow(b, n, mod) % mod
	else:
		x1 = pow(a, n, a - b)
		x2 = pow(b, n, a - b)
		gc = math.gcd((x1 + x2) % (a - b), a - b)
		return gc % mod
t = int(input())
while t >= 1:
	(a, b, n) = input().split()
	a = int(a)
	b = int(b)
	n = int(n)
	print(gcc(a, b, n) % mod)
	t = t - 1


def gcd(a, b, n):
	if a == b:
		return (power(a, n, 1000000007) + power(b, n, 1000000007)) % 1000000007
	num = a - b
	i = 1
	can = 1
	while i * i <= num:
		if num % i == 0:
			temp = (power(a, n, i) + power(b, n, i)) % i
			if temp == 0:
				can = max(can, i)
			temp = (power(a, n, num // i) + power(b, n, num // i)) % (num // i)
			if temp == 0:
				can = max(can, num // i)
		i += 1
	return can % 1000000007

def power(num, p, d):
	res = 1
	while p:
		if p % 2 == 0:
			num = num % d * (num % d) % d
			p = p // 2
		else:
			p -= 1
			res = res % d * (num % d) % d
	return res
t = int(input())
while t:
	t -= 1
	(x, y, n) = map(int, input().split())
	print(gcd(x, y, n))


mod = 10 ** 9 + 7

def power(base, p, m):
	res = 1
	while p >= 1:
		if p & 1:
			res = res % m * (base % m) % m
			p -= 1
		else:
			base = base % m * (base % m) % m
			p //= 2
	return res
for i in range(int(input())):
	(a, b, n) = map(int, input().split())
	diff = abs(a - b)
	if diff == 0:
		print((power(a, n, mod) + power(b, n, mod)) % mod)
		continue
	j = 1
	fin = 0
	while j * j <= diff:
		if diff % j == 0:
			ans = (power(a, n, j) + power(b, n, j)) % j
			if ans == 0:
				fin = max(j, fin)
			ans = (power(a, n, diff // j) + power(b, n, diff // j)) % (diff // j)
			if ans == 0:
				fin = max(fin, diff // j)
		j += 1
	print(fin % mod)


MAX = pow(10, 9) + 7

def power(a, n, mod):
	res = 1
	while n:
		if n % 2:
			res = a % mod * res % mod % mod
			n -= 1
		else:
			a = a % mod * a % mod % mod
			n /= 2
	return res

def GCD(a, b, n):
	if a == b:
		return (power(a, n, MAX) + power(b, n, MAX)) % MAX
	candidate = 1
	num = a - b
	i = 1
	while i * i <= num:
		if num % i == 0:
			tmp = (power(a, n, i) + power(a, n, i)) % i
			if tmp == 0:
				candidate = max(candidate, i)
			tmp = (power(a, n, num // i) + power(a, n, num // i)) % (num // i)
			if tmp == 0:
				candidate = max(candidate, num // i)
		i += 1
	return candidate
for _ in range(int(input())):
	(a, b, n) = list(map(int, input().split()))
	print(GCD(a, b, n))


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	diff = a - b
	if diff == 0:
		print((pow(a, n, 1000000007) + pow(b, n, 1000000007)) % 1000000007)
		continue
	add = (pow(a, n, diff) + pow(b, n, diff)) % diff
	import math
	print(math.gcd(add, diff) % 1000000007)


import math
try:

	def power(x, y, p):
		res = 1
		x = x % p
		if x == 0:
			return 0
		while y > 0:
			if y & 1 == 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res
	p = 1000000007
	for _ in range(int(input())):
		(a, b, n) = map(int, input().split())
		if a == b:
			ans = (power(a, n, p) + power(b, n, p)) % p
			print(ans)
		else:
			ans = math.gcd((power(a, n, a - b) + power(b, n, a - b)) % (a - b), a - b)
			print(ans)
except:
	print('fuck')


def power(a, m, mod):
	ans = 1
	while m > 0:
		if m & 1:
			ans = ans % mod * (a % mod) % mod
			m -= 1
		else:
			a = a % mod * (a % mod) % mod
			m //= 2
	return ans

def gcd(a, b, m):
	res = 1
	modd = 1000000007
	if a == b:
		return (power(a, m, modd) + power(b, m, modd)) % modd
	n = abs(a - b)
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			x = (power(a, m, i) + power(b, m, i)) % i
			if x == 0:
				res = max(res, i)
			x = (power(a, m, n // i) + power(b, m, n // i)) % (n // i)
			if x == 0:
				res = max(res, n // i)
	return res % 1000000007
for _ in range(int(input())):
	(a, b, m) = map(int, input().split())
	print(gcd(a, b, m))


from math import gcd
mod = 1000000007
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	v = a - b
	if v == 0:
		print((pow(a, n, mod) + pow(b, n, mod)) % mod)
		continue
	v1 = (pow(a, n, v) + pow(b, n, v)) % v
	print(gcd(v1, v) % mod)


import math
M = 10 ** 9 + 7
T = int(input())
for i in range(T):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(pow(a, n) * 2 % M)
	else:
		print(math.gcd(pow(a, n, a - b) + pow(b, n, a - b), a - b) % M)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
import math
M = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(pow(a, n) * 2 % M)
	else:
		print(math.gcd(pow(a, n, a - b) + pow(b, n, a - b), a - b) % M)


import math

def power(a, b, mod):
	res = 1
	while b > 0:
		if b % 2 == 0:
			a = a * a % mod
			b = b // 2
		else:
			res = res * a % mod
			b = b - 1
	return res
t = int(input())
for test in range(t):
	(a, b, n) = map(int, input().split())
	num = abs(a - b)
	if a == b:
		num = (power(a, n, 10 ** 9 + 7) + power(b, n, 10 ** 9 + 7)) % (10 ** 9 + 7)
		print(num)
	else:
		arr = []
		for i in range(1, math.floor(math.sqrt(num)) + 1):
			if num % i == 0:
				arr.append(i)
				arr.append(num // i)
		ans = -1
		for i in arr:
			a1 = power(a, n, i)
			a2 = power(b, n, i)
			if (a1 + a2) % i == 0:
				ans = max(ans, i)
		print(ans % (10 ** 9 + 7))


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
mod = 1000000007
import math
t = int(input())
for i in range(t):
	(a, b, n) = tuple(map(int, input().split()))
	if a == b:
		print((pow(a, n, mod) + pow(b, n, mod)) % mod)
		continue
	ans = math.gcd((power(a, n, a - b) + power(b, n, a - b)) % (a - b), a - b) % mod
	print(ans)


mod = 1000000007
import math
t = int(input())
for i in range(t):
	(a, b, n) = tuple(map(int, input().split()))
	if a == b:
		print((pow(a, n, mod) + pow(b, n, mod)) % mod)
		continue
	d = a - b
	ans = 1
	for j in range(1, int(math.sqrt(d)) + 1):
		if d % j == 0:
			temp = (pow(a, n, j) + pow(b, n, j)) % j
			if temp == 0:
				ans = max(ans, j)
			s = d // j
			temp = (pow(a, n, s) + pow(b, n, s)) % s
			if temp == 0:
				ans = max(ans, s)
	print(ans)


mod = 1000000007
import math

def go(a, b, n):
	if a == b:
		return (pow(a, n, mod) + pow(b, n, mod)) % mod
	d = a - b
	ans = 1
	for j in range(1, int(math.sqrt(d)) + 1):
		if d % j == 0:
			temp = 0
			temp = (pow(a, n, j) + pow(b, n, j)) % j
			if temp == 0:
				ans = max(ans, j)
			s = d // j
			temp = (pow(a, n, s) + pow(b, n, s)) % s
			if temp == 0:
				ans = max(ans, s)
	return ans % mod
t = int(input())
while t:
	(a, b, n) = tuple(map(int, input().split()))
	print(go(a, b, n))
	t -= 1


import math

def getpower(base, power, mod):
	return pow(base, power, mod)

def gcd(a, b, power, mod):
	if a == b:
		return (getpower(a, power, mod) + getpower(b, power, mod)) % mod
	num = a - b
	candidate = 1
	for i in range(1, int(math.sqrt(num)) + 1):
		if num % i == 0:
			inter = (getpower(a, power, i) + getpower(b, power, i)) % i
			if inter == 0:
				candidate = max(candidate, i)
			inter = (getpower(a, power, num // i) + getpower(b, power, num // i)) % (num // i)
			if inter == 0:
				candidate = max(candidate, num // i)
	return candidate
testcase = int(input())
while testcase:
	(a, b, power) = map(int, input().split())
	mod = 10 ** 9 + 7
	print(gcd(a, b, power, mod))
	testcase -= 1


import math
mod = 1000000007

def power(a, n, m):
	ans = 1
	while n:
		if n % 2 == 0:
			n //= 2
			a = a % m * (a % m) % m
		else:
			ans = ans % m * (a % m) % m
			n -= 1
	return ans
t = int(input())
for i in range(t):
	(a, b, n) = tuple(map(int, input().split()))
	if a == b:
		print((power(a, n, mod) + power(b, n, mod)) % mod)
	else:
		print(math.gcd(pow(a, n, abs(a - b)) + pow(b, n, abs(a - b)), abs(a - b)) % mod)


from math import gcd
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	ans = 1
	x = a
	y = a - b
	if (a - b) % 2 == 0:
		y = y // 2
		ans = 2
	while n > 0:
		k = gcd(x, y)
		if k == 1:
			break
		ans = ans * k % mod
		x = k
		y = y // k
		n -= 1
	print(ans)


import sys, io, os, math, time
from math import ceil, log, inf, floor, sqrt
from itertools import permutations
import datetime
mod = 1000000007
mod1 = 998244353

def intinp():
	return int(sys.stdin.readline())

def strinp():
	return sys.stdin.readline()

def arrinp():
	return list(map(int, sys.stdin.readline().strip().split()))

def mulinp():
	return map(int, sys.stdin.readline().strip().split())

def flush():
	return sys.stdout.flush()

def power_two(x):
	return 1 << x

def power(a, n, d):
	res = 1
	while n:
		if n & 1:
			res = res % d * (a % d) % d
			n -= 1
		else:
			a = a % d * (a % d) % d
			n = n // 2
	return res

def gcd(a, b, n):
	if a == b:
		return (power(a, n, mod) + power(b, n, mod)) % mod
	candidate = 1
	num = abs(a - b)
	limit = int(sqrt(num))
	for i in range(1, limit + 1):
		if num % i == 0:
			tmp = (power(a, n, i) + power(b, n, i)) % i
			if tmp == 0:
				candidate = max(candidate, i)
			tmp = (power(a, n, num // i) + power(b, n, num // i)) % (num // i)
			if tmp == 0:
				candidate = max(candidate, num // i)
	return candidate % mod

def solution():
	(a, b, n) = mulinp()
	print(gcd(a, b, n))
	return

def main():
	tc = intinp()
	while tc:
		solution()
		tc -= 1
main()


import math

def powwer2(a, b, m):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans = ans * a % m
		a = a * a % m
		b = b // 2
	return ans
t = int(input())
M = 1000000007
for i in range(t):
	(a, b, n) = list(map(int, input().split()))
	d = a - b
	p = 0
	if d == 0:
		p = (powwer2(a, n, M) + powwer2(b, n, M)) % M
	else:
		p = (powwer2(a, n, d) + powwer2(b, n, d)) % d
	g = math.gcd(p, d) % M
	print(g)


import math
from math import gcd, sqrt, floor, factorial, ceil
from bisect import bisect_left, bisect_right
import bisect
import sys
from sys import stdin, stdout
import os
sys.setrecursionlimit(pow(10, 7))
import collections
from collections import defaultdict, Counter
from statistics import median
from queue import Queue
inf = float('inf')
from operator import neg
mod = pow(10, 9) + 7

def factors(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return [i] + factors(n // i)
	return [n]

def check(a, b, n, number):
	theta1 = pow(a, n, number)
	theta2 = pow(b, n, number)
	return (theta1 + theta2) % number == 0
t = int(input())
for i in range(t):
	(a, b, n) = map(int, input().split())
	if a == b:
		theta1 = pow(a, n, mod)
		theta2 = pow(b, n, mod)
		ans = theta1 + theta2
		print(ans % mod)
		continue
	prime_fac = Counter(factors(a - b))
	maxa = 1
	for i in prime_fac:
		for j in range(prime_fac[i]):
			maxa *= i
			if not check(a, b, n, maxa):
				maxa //= i
				break
	print(maxa % mod)


def power(a, n, d):
	i = 1
	while n >= 1:
		if n % 2 != 0:
			i = i % d * (a % d) % d
			n -= 1
		else:
			a = a % d * (a % d) % d
			n //= 2
	return i % d

def funct(a, b, n):
	if a == b:
		return power(a, n, 10 ** 9 + 7) + power(b, n, 10 ** 9 + 7)
	i = 1
	l = abs(a - b)
	candidate = 1
	while i * i <= l:
		if l % i == 0:
			temp = (power(a, n, i) + power(b, n, i)) % i
			if temp == 0:
				candidate = max(candidate, i)
			temp = (power(a, n, l // i) + power(b, n, l // i)) % (l // i)
			if temp == 0:
				candidate = max(candidate, l // i)
		i += 1
	return candidate
t = int(input())
for i in range(t):
	(a, b, n) = map(int, input().split())
	print(funct(a, b, n))


from math import gcd

def main():
	try:
		for _ in range(int(input())):
			(a, b, n) = list(map(int, input().split()))
			sub = abs(b - a)
			if sub != 0:
				c = (pow(a, n, sub) + pow(b, n, sub)) % sub
				print(gcd(sub, c) % (7 + 10 ** 9))
			else:
				sub = 7 + 10 ** 9
				print((pow(a, n, sub) + pow(b, n, sub)) % sub)
	except:
		pass
main()


def power(num, p, D, m):
	if p == 0:
		return 1
	elif p == 1:
		return num % m
	elif p in D:
		return D[p]
	else:
		D[p] = power(num, p // 2, D, m) % m * (power(num, p - p // 2, D, m) % m) % m
		return D[p]

def gcd(a, b, m):
	if b == 0:
		return a % m
	else:
		return gcd(b, a % b, m) % m
T = int(input())
ans = []
m = 10 ** 9 + 7
for _ in range(T):
	(a, b, n) = [int(i) for i in input().split()]
	if a == b:
		ans.append(power(a, n, {}, m) + power(a, n, {}, m) % m)
	else:
		x = power(a, n, {}, abs(a - b))
		y = power(b, n, {}, abs(a - b))
		x = (x + y) % abs(a - b)
		y = abs(a - b)
		ans.append(gcd(y, x, m) % m)
for i in ans:
	print(i)


mod = 10 ** 9 + 7

def power(a, n, m):
	if n == 0:
		return 1
	res = 1
	while n:
		if n % 2 == 1:
			res = res * a % m
			n -= 1
		else:
			a = a * a % m
			n //= 2
	return res % m

def gcd(a, b):
	if b == 0:
		return a % mod
	return gcd(b, a % b) % mod

def calGCD(a, b, n):
	if a == b:
		return (power(a, n, mod) + power(a, n, mod)) % mod
	x = power(a, n, abs(a - b))
	y = power(b, n, abs(a - b))
	x = (x + y) % abs(a - b)
	y = abs(a - b)
	return gcd(y, x) % mod
try:
	t = int(input())
	for _ in range(t):
		(a, b, n) = map(int, input().split())
		print(calGCD(a, b, n))
except:
	pass


mod = int(1000000000.0 + 7)

def power(x, y, MOD):
	ans = 1
	while y > 0:
		if y & 1:
			ans = ans * x % MOD
		y = y >> 1
		x = x * x % MOD
	return ans

def gcd(a, b):
	if a < b:
		swap(a, b)
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t > 0:
	ar = tuple(map(int, input().split()))
	a = ar[0]
	b = ar[1]
	n = ar[2]
	t -= 1
	d = a - b
	if d == 0:
		ans = (power(a, n, mod) + power(b, n, mod)) % mod
		print(ans)
		continue
	p = (power(a, n, d) + power(b, n, d)) % d
	ans = gcd(d, p) % mod
	print(int(ans))


from math import gcd
t = int(input())
MOD = int(1000000000.0 + 7)
for _ in range(t):
	(a, b, n) = map(int, input().split())
	if a == b:
		print((pow(a, n, MOD) + pow(b, n, MOD)) % MOD)
		continue
	aa = pow(a, n, a - b)
	bb = pow(b, n, a - b)
	mm = (aa + bb) % MOD
	print(gcd(aa + bb, a - b))


def fast_power(x, y, mod):
	if x == 0:
		return 0
	res = 1
	while y > 0:
		if y % 2 != 0:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for tt in range(int(input())):
	(a, b, n) = map(int, input().split())
	mod = 10 ** 9 + 7
	r = abs(a - b)
	if r == 0:
		print((fast_power(a, n, mod) + fast_power(b, n, mod)) % mod)
	else:
		r1 = fast_power(a, n, r)
		r2 = fast_power(b, n, r)
		x = (r1 + r2) % r
		print(gcd(x, r) % mod)


import math
m = 10 ** 9 + 7
t = int(input())

def modExp(a, b, m):
	ans = 1
	a = a % m
	while b > 0:
		if b & 1:
			ans = ans % m * (a % m) % m
		a = a % m * (a % m) % m
		b = b >> 1
	return ans % m
for i in range(0, t):
	l = list(map(int, input().split()))
	a = l[0]
	b = l[1]
	n = l[2]
	if a == b:
		ans = (modExp(a, n, m) + modExp(b, n, m)) % m
		print(ans)
	else:
		val1 = (modExp(a, n, a - b) + modExp(b, n, a - b)) % (a - b)
		val2 = a - b
		val3 = math.gcd(val1, val2) % m
		print(val3)


from math import gcd
MOD = 1000000007

def main():
	for _ in range(int(input())):
		(a, b, n) = [int(x) for x in input().split()]
		if a == b:
			print((pow(a, n, MOD) + pow(b, n, MOD)) % MOD)
		else:
			x = pow(a, n, a - b)
			y = pow(b, n, a - b)
			print(gcd(x + y, a - b) % MOD)
main()


def power(a, b, MOD):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % MOD
		a = a * a % MOD
		b = b >> 1
	return res
MOD2 = 1000000007
t = int(input())
while t > 0:
	(a, b, n) = input().split()
	(a, b, n) = (int(a), int(b), int(n))
	x = a - b
	if x == 0:
		print(int((power(a, n, MOD2) + power(b, n, MOD2)) % MOD2))
		t -= 1
		continue
	options = []
	for i in range(1, x):
		if i * i > x:
			break
		if x % i == 0:
			options.append(i)
			if x / i != i:
				options.append(int(x / i))
	options.sort()
	ans = 1
	for val in options:
		if int((power(a, n, val) + power(b, n, val)) % val) == 0:
			ans = val
	print(int(ans % MOD2))
	t -= 1


def power(a, n, mod):
	if n == 0:
		return 1
	if n == 1:
		return a
	res = power(a, int(n / 2), mod)
	if n % 2 == 0:
		return res % mod * res % mod % mod
	res = res % mod * res % mod % mod
	res = a % mod * res % mod
	return res

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def solve():
	(a, b, n) = map(int, input().split())
	y = a - b
	mod = 1000000007
	if y == 0:
		ans = power(a, n, mod) + power(b, n, mod)
		ans = ans % mod
		print(ans)
		return
	result = power(a, n, y) + power(b, n, y)
	result = gcd(y, result)
	result = result % mod
	print(result)
t = input()
t = int(t)
for k in range(t):
	solve()


import math
import sys
MAX = 1000000007

def countOnes(n):
	arr = []
	while n != 0:
		if n & 1 == 1:
			arr.append(1)
		else:
			arr.append(0)
		n = n >> 1
	return arr

def binMod(num, mod, binN):
	bd = [num % mod]
	while len(bd) <= len(binN):
		bd.append(bd[-1] ** 2 % mod)
	total = 1
	for i in range(len(binN)):
		if binN[i] == 1:
			total *= bd[i]
	return total

def solve(a, b, n):
	binN = countOnes(n)
	mod = abs(a - b)
	if mod == 0:
		mod = MAX
	aPrime = binMod(a, mod, binN)
	bPrime = binMod(b, mod, binN)
	final = aPrime + bPrime
	if mod == MAX:
		return final % MAX
	return math.gcd(final, mod) % MAX

def readinput():
	tc = int(sys.stdin.readline().rstrip())
	for _ in range(tc):
		(a, b, n) = map(int, sys.stdin.readline().rstrip().split(' '))
		print(solve(a, b, n))
readinput()


import math
m = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if abs(a - b) == 0:
		print(pow(a, n, m) + pow(b, n, m) % m)
	else:
		d = pow(a, n, abs(a - b)) + pow(a, n, abs(a - b))
		print(math.gcd(d, abs(a - b)))


from math import gcd

def expo(a, b, m):
	if b == 0:
		return 1
	elif b % 2 == 0:
		val = expo(a, b // 2, m)
		return val * val % m
	else:
		res = expo(a, b - 1, m)
		return res * a % m
m = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b, n) = [int(x) for x in input().split()]
	if a == b:
		y = expo(b, n, m)
		print((y + y) % m)
	else:
		m2 = abs(a - b)
		x = expo(a, n, m2)
		y = expo(b, n, m2)
		print(gcd(x + y, m2))


import math
mod = 1000000007

def bruteForce(a, b, n):
	if a == b:
		res = pow(a, n, mod)
		return res % mod + res % mod
	d = abs(b - a)
	(a, b) = (pow(a, n, d), pow(b, n, d))
	ab = a + b
	r = math.gcd(ab, d)
	return r % mod

def power(a, n, m):
	result = 1
	while n > 0:
		a = a % m
		if n % 2 == 1:
			result = result % m * a % m
			n -= 1
		a = a * a % m
		n //= 2
	return result % m

def checkGCD(a, b, n, d):
	a = power(a, n, d) % d
	b = power(b, n, d) % d
	aplusb = (a + b) % d
	if aplusb == 0:
		return True
	return False

def solve(a, b, n):
	if a == b:
		return 2 * power(b, n, mod) % mod % mod
	diff = abs(a - b)
	res = 1
	i = 1
	while i * i <= diff:
		if diff % i == 0:
			if checkGCD(a, b, n, i):
				res = max(res, i)
			if checkGCD(a, b, n, diff // i):
				res = max(res, diff // i)
		i += 1
	return res % mod
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	print(solve(a, b, n))


import math
mod = 1000000007

def bruteForce(a, b, n):
	if a == b:
		res = pow(a, n, mod)
		return res % mod + res % mod
	d = abs(b - a)
	(a, b) = (pow(a, n, d), pow(b, n, d))
	ab = a + b
	r = math.gcd(ab, d)
	return r % mod
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	print(bruteForce(a, b, n))