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
# Karan Singh
# (a/b)%c means c = c * b
#  y = (a%c)/b 
#  y =  (y + n)%n

t = input()
while t>0 :
	t = t - 1
	x,m,n=map(int,raw_input().split())
	if(x==1):
		print((m+1)%n)
	else:
		n = n*(x-1) 
		y = (pow(x,m+1,n)-1)/(x-1)
		print(y+n)%n