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.

----- Sample Input 1 ------ 
3
1 10
2 12
100 10000
----- Sample Output 1 ------ 
1/1
2/3
4301/9525

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	(n, m) = map(int, input().rstrip().split())
	num = 1
	den = 1
	for i in range(2, n + 1):
		num = (num + den) % m
		den = (num + den) % m
	print(str(num % m) + '/' + str(den % m))


def main():
	T = eval(input())
	for t in range(T):
		(n, m) = tuple([int(x) for x in input().split()])
		(a, b) = (0, 1)
		for i in range(n):
			(a, b) = ((a + b) % m, a)
			(a, b) = ((a + b) % m, a)
		num = str(b)
		den = str(a)
		print(num + '/' + den)
main()


for tc in range(int(input().strip())):
	(N, M) = map(int, input().strip().split())
	(a, b) = (1, 1)
	for i in range(1, N):
		(a, b) = ((a + b) % M, (a + 2 * b) % M)
	print(a, end='/')
	print(b)


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	(num, den) = (1, 1)
	for i in range(1, n):
		num = num + den
		den = den + num
		num = num % m
		den = den % m
	print(f'{num}/{den}')


def square(m1, mod):
	return mul(m1, m1, mod)

def mul(m1, m2, mod):
	return [[(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % mod, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % mod], [(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % mod, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % mod]]

def fib(n, mod):
	if n == 0:
		return 1
	ans = [[1, 1], [1, 0]]
	tm = [[1, 1], [1, 0]]
	exp = 1
	up = 1
	while 1:
		if exp == n:
			return ans[0][0]
		if exp + up > n:
			tm = [[1, 1], [1, 0]]
			up = 1
		ans = mul(ans, tm, mod)
		tm = square(tm, mod)
		exp += up
		up *= 2
T = int(input())
while T > 0:
	T -= 1
	data = input().split()
	(n, m) = (int(data[0]), int(data[1]))
	p = fib(2 * (n - 1), m)
	q = fib(2 * n - 1, m)
	print('%d/%d' % (p, q))


def mod_mul(m1, m2, mod):
	return [[(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % mod, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % mod], [(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % mod, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % mod]]

def solve():
	(n, mod) = map(int, input().split())
	n = 2 * n - 1
	ans = [[1, 1], [1, 0]]
	tm = [[1, 1], [1, 0]]
	exp = 1
	up = 1
	while 1:
		if exp == n:
			return ans
		if exp + up > n:
			tm = [[1, 1], [1, 0]]
			up = 1
		ans = mod_mul(ans, tm, mod)
		tm = mod_mul(tm, tm, mod)
		exp += up
		up *= 2
for _ in range(int(input())):
	p = solve()
	print('%d/%d' % (p[0][1], p[0][0]))


def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	(n, m) = li()
	p = q = 1
	nn = n - 1
	for i in range(nn):
		t = (p + q) % m
		(p, q) = (t, (t + q) % m)
	print(f'{p}/{q}')


for tc in range(int(input().strip())):
	(n, MOD) = [int(i) for i in input().split()]
	(num, den) = (1, 1)
	for i in range(n - 1):
		num += den
		den += num
		num %= MOD
		den %= MOD
	print(str(num % MOD) + '/' + str(den % MOD))


def multiply(m1, m2, mod):
	return [[(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % mod, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % mod], [(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % mod, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % mod]]

def fibo(n, mod):
	if n == 0:
		return 1
	res = [[1, 1], [1, 0]]
	temp = [[1, 1], [1, 0]]
	exp = factor = 1
	while True:
		if exp == n:
			return res
		if exp + factor > n:
			temp = [[1, 1], [1, 0]]
			factor = 1
		res = multiply(res, temp, mod)
		temp = multiply(temp, temp, mod)
		exp += factor
		factor *= 2
for t in range(0, int(input())):
	(n, mod) = map(int, input().split())
	mat = fibo(2 * n - 1, mod)
	print('%d/%d' % (mat[0][1], mat[0][0]))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(a, b) = (1, 1)
	for j in range(1, n):
		a += b
		b += a
		a %= m
		b %= m
	print(f'{a}/{b}')