Given three integers x, m and n. Evaluate (1 + x + x^ 2 + .. + x^ m)  (mod n)


Input

First line of the input contains a single integer T representing number of test cases that follow.


For next T lines, each line contains three space separated integers x, m and n.


Output

Output exactly T lines each containing the answer to the corresponding test case.


Constraints

1 ≤ T ≤ 1000 
1 ≤ x, n, m ≤ 10^16


Example
Input:
1
3 2 5

Output:
3
def getpow(x, n, mod) :
    if n == 0:
        return 1
    if n == 1 :
        return x
    z = getpow(x, n/2, mod)
    if n % 2 == 0 :
        return (z*z)%mod
    return (z*z*x)%mod


 
t = int(raw_input())
for i in xrange(t):
    s = raw_input()
    nums = [int(n) for n in s.split()]
    x = nums[0]
    m = nums[1]
    n = nums[2]
    if x == 1:
        z1 = (m+1)%n
        print z1
        continue
    mod =  n*(x-1)
    z1 = getpow(x, m+1,mod)
    z1 -= 1
    z1 += mod
    z1 %= mod
    z1 /= (x-1)
    print z1