import numpy as np
from numpy import linalg as LA
from fractions import gcd
 
def expo(A , m):
	if m==1:
		return A
 
	#print A
	p = 1
	for x in np.nditer(A):
		p = gcd(p,x)
 
	A /= p
	#A /= gcd( gcd(A[1][0],A[1][1] ),gcd(A[0][0],A[0,1] ) )
	C = np.matrix( "0,0 ; 0,0")
	#print C
	if ~m&1:
		C =  expo(A,m/2)*expo(A,m/2)
		return C
	else:
		C = A*expo(A,m/2)
		return C
 
 
 
 
A = np.matrix( "1,1 ; 1,2")
B = np.matrix( " 1;1")
 
t= input()
while t:
	t-=1
	n,mod = map(int,raw_input().split())
	if n==1:
		print "1/1"
	else:
		print (expo(A,n-1)*B) % mod
 
 
 

aW1wb3J0IG51bXB5IGFzIG5wCmZyb20gbnVtcHkgaW1wb3J0IGxpbmFsZyBhcyBMQQpmcm9tIGZyYWN0aW9ucyBpbXBvcnQgZ2NkCgpkZWYgZXhwbyhBICwgbSk6CglpZiBtPT0xOgoJCXJldHVybiBBCgkKCSNwcmludCBBCglwID0gMQoJZm9yIHggaW4gbnAubmRpdGVyKEEpOgoJCXAgPSBnY2QocCx4KQoJCQoJQSAvPSBwCgkjQSAvPSBnY2QoIGdjZChBWzFdWzBdLEFbMV1bMV0gKSxnY2QoQVswXVswXSxBWzAsMV0gKSApCglDID0gbnAubWF0cml4KCAiMCwwIDsgMCwwIikKCSNwcmludCBDCglpZiB+bSYxOgoJCUMgPSAgZXhwbyhBLG0vMikqZXhwbyhBLG0vMikKCQlyZXR1cm4gQwoJZWxzZToKCQlDID0gQSpleHBvKEEsbS8yKQoJCXJldHVybiBDCgkKCgoKQSA9IG5wLm1hdHJpeCggIjEsMSA7IDEsMiIpCkIgPSBucC5tYXRyaXgoICIgMTsxIikKCnQ9IGlucHV0KCkKd2hpbGUgdDoKCXQtPTEKCW4sbW9kID0gbWFwKGludCxyYXdfaW5wdXQoKS5zcGxpdCgpKQoJaWYgbj09MToKCQlwcmludCAiMS8xIgoJZWxzZToKCQlwcmludCAoZXhwbyhBLG4tMSkqQikgJSBtb2QKCQkKCQo=

MQo1MCAxMDAwCg==

1
50 1000