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 powMod(a,b,m):
	if(b==0) : return 1
	if(b==1) : return a%m
	if(b%2) : return (a*powMod(a*a%m, b/2, m))%m
	else : return powMod(a*a%m, b/2, m)
t = int(raw_input())
while(t):
	t-=1
	inp = raw_input().split(' ')
	x = int(inp[0])
	m = int(inp[1])
	n = int(inp[2])
	if(x==1) : print (m+1)%n
	else : print ((powMod(x,m+1,n*(x-1))-1+n*(x-1))%(n*(x-1)))/(x-1)