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 pwr(x,n,mod):
	if n==0:
		return 1
	temp=pwr(x,n/2,mod)
	temp=(temp*temp)%mod
	if n%2==1:
		temp=(temp*x)%mod
	return temp
t=int(raw_input())
while t:
	t-=1	
	x,m,n=[int(i) for i in raw_input().split()]
	# print x
	
	if x==1:
		print (m+1)%n
		continue
	den = x-1
	mod = n*(den)
	num = pwr(x,m+1,mod)
	num=num-1
	num=num%mod
	# print mod
	# print num,den
	if num<0:
		num=num+mod
	print num/den