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).
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.
For each test case, print a single line containing one integer — the required GCD modulo 10^9+7.
Can anyone please give me the idea to solve this problem ??