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
t=int(input())
 
for i in range(0,t):
    x,m,n=map(int,raw_input().split(" "))
    if x==1:
        ans=(m+1)%n
        ans=int(ans)
    else:
        ans=pow(x,m+1,(x-1)*n)
        ans=(ans+((x-1)*n)-1)
        ans=ans%((x-1)*n)
        ans=ans/(x-1)
        ans=int(ans)
    print(ans)