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 f(x,m,n):
	d=1
	while(m):
		if(m%2==1):
			d=(d*x)%n
		x=(x*x)%n
		m=m/2
	return d%n
	
t=int(raw_input())
while(t):
	x,m,n=raw_input().split()
	x=long(x)
	m=long(m)
	n=long(n)
	if(x==1):
		ans=(m+1)%n
	else:
		n=n*(x-1)
		ans=(f(x,m+1,n)-1)%n
		ans=ans/(x-1)
	print ans
	t=t-1