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
import math
t= input()
t=int(t)

while (t > 0):
	t=t-1
	z = raw_input()
	z=z.split()
	x = int(z[0])
	m =int(z[1])
	n=int(z[2])
	if (x==1):
		print (m+1)%n
	else:
		n=n*(x-1)
		powx = pow(x,m+1,n)-1
		powx= (powx+n)%n
		print powx/(x-1)