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 modulo(a,c,b):
    x=1
    y=a
    while c>0:
        if c%2!=0:
            x=(x*y)%b
        y=(y*y)%b
        y%=b
        c=int(c/2)
    return (x-1)%b
t=int(raw_input())
for i in range(t):
    a,b,c=map(int,raw_input().split(" "))
    if a==1:
        g=((b+1)%c)
    else:
        g=modulo(a,b+1,(a-1)*c)
        g+=(a-1)*c
        g%=(a-1)*c
        g=g/(a-1)
        g=int(g)
    print(g)