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
# your code goes here

t = input()
t = int(t)

for i in range (t):
	x, m, n = raw_input().split()
	x = int(x)
	m = int(m)
	n = int(n)
	if(x == 1):
		ans = (m+1)%n
		print ans
		continue
	
	n = n*(x - 1)
	ans = pow(x, m+1, n)
	ans = ans + n - 1
	ans = ans%n
	
	ans = ans/(x - 1)
	
	print ans