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 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 findNthPower(n, mod):
    A = [[1, 1], [1, 0]]
    if n == 1:
        return A
    r = findNthPower(n / 2, mod)
    r = multiply(r, r, mod)
    if n % 2 == 1:
        r = multiply(r, A, mod)
    return r


def solve(n, m):
    r = findNthPower(2*n-1, m)
    return "%s/%s" % (r[0][1], r[0][0])


def main():
    for _ in range(int(raw_input())):
        n, m = map(int, raw_input().split())
        print("%s" % solve(n, m))


if __name__ == "__main__":
    main()