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
#!/usr/bin/env python
#try:
t=int(raw_input())
while t>0:
	x,m,n=raw_input().split()
	#x,m,n= int(u) for u in raw_input().strip().split()
	#lis = map(int, raw_input().split())
	x=int(x)
	m=int(m)
	n=int(n)
	ans=0
	if x==1:print (m+1)%n
	else:
		#for i in range (0,m+1):
		#	ans= (ans + pow(x,i,n))%n
		print ((pow(x,m+1,(x-1)*n)-1+(x-1)*n)%((x-1)*n))/(x-1)
	t=t-1
#except:
#	pass