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
test_cases = int(raw_input())

while(test_cases):
	#we need to calculate (a/b)%c
	#also equal to (a%bc)/b
	#here a = x^(m+1) - 1, b= x-1 and c = n
	values = raw_input().split()
	x = int(values[0])
	m = int(values[1])
	n = int(values[2])

	if(x==1):
		print (m+1)%n
	else:
		newmod = n*(x-1)
		solution = pow(x, m+1, newmod) -1
		solution = (solution+newmod)%newmod;
		solution = solution/(x-1)
		print solution


	test_cases-=1