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
# your code goes here
def modexpo(x,m,n):
    if(m>1):
        ans=modexpo(x,m/2,n)
        ans=(ans*ans)%n
        if((m%2)== 1):
            ans=(ans*x)%n
        return ans
    else :
        return x


t=int(input())
while t>0 :
    t=t-1
    x,m,n = map(int, raw_input().split())
    if x==1 :
        answer=(m+1)%n
    else :
        n=n*(x-1)
        answer=modexpo(x%n,m+1,n)
        answer=(answer-1+n)%n
        answer=answer/(x-1)
    print answer