The electrical resistance is the opposition to the passage of electric current. If two resistors with resistance R1 and R2 are connected to each other, the resultant resistance R depends on how their ends are connected. If they are connected in Series, they simply add up to give R = R1 + R2. If they are connected in Parallel, its given by the equation 1/R = 1/R1 + 1/R2. This is shown below.



We have a long circuit of resistors of one unit resistance each ( Ri = 1 ) having N blocks. Each block has 2 resistors as shown in the figure below. For a circuit with only one block (N=1), the equivalent resistance at the ends on left-side is R = 1 ( note that the right-most horizontally aligned resistor has no influence, as its not part of any simple path between the two left ends ). For a circuit with two blocks (N=2), its 2/3 units. This is shown in the figure below.



Given N, find the resistance A/B at the left ends of the circuit having N blocks. The values can be huge, so reduce the fraction A/B to lowest terms P/Q, where greatest_common_divisor_of (P,Q) = 1 and print (P%M)/(Q%M) for a given modulo M.


Input
First line contains T ( number of test cases, 1 ≤ T ≤ 10 ). Each of the next T lines contains N M ( 1 <= N <= 10^6 and 2 <=M <= 2^30 )


Output
For each test case, output the equivalent resistance at the left ends, in the form (P%M)/(Q%M) as explained above, in a separate line.


Example

Input:
3
1 10
2 12
100 10000

Output:
1/1
2/3
4301/9525
def multiplyMatrices( A, B, K ):	#e.g. A = [ [1, 1], [1, 0] ], B = [ [ F(n) ], [ F(n-1) ] ]
	C = []
	if len(A[0]) != len(B):
		raise RuntimeError("These matrices cant be multiplied")
	for i in xrange(len(A)):
		C.append([])
		for k in xrange(len(B[0])):
			sum = 0
			for j in xrange(len(A[0])):
				sum += A[i][j] * B[j][k]
			C[i].append(sum%K)
	return C

def findNthPowerModK( M , n, k ):
	if n == 1:
		return M;
	R = findNthPowerModK( M , n/2, k )
	R = multiplyMatrices(R, R, k)  # matrix multiplication
	if n%2 == 1:
		R = multiplyMatrices(R, M, k)  # matrix multiplication
	return R




T = int(raw_input())


while T>0:
	T-=1
	N, M = map(int, raw_input().split())
	"""
	R = resistance_of_blocks(N)
	print(str(R[0])+"/"+str(R[1]))
	"""
	"""
	a=1
	b=1
	for i in xrange(2*(N-1)):
		c = a
		a = b
		b = (c+b) % M
	print(str(a%M)+"/"+str(b%M))
	"""
	if N==1:
		print("1/1")
		continue
	The_Famous_Fibonacci_Matrix = [ [1, 1], [1, 0] ]
	The_Nth_Fibonacci_Matrix = findNthPowerModK(The_Famous_Fibonacci_Matrix, 2*(N-1), M)
	The_F1_F0_Fib_Mat = [ [ 1 ], [ 1 ] ]
	The_Result_Matrix = multiplyMatrices( The_Nth_Fibonacci_Matrix, The_F1_F0_Fib_Mat, M )
	
	print(str(The_Result_Matrix[1][0]%M)+"/"+str(The_Result_Matrix[0][0]%M))