Resistance

All submissions for this problem are available.
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 leftside is R = 1 ( note that the rightmost 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
Author:  flying_ant 
Tester:  Maksflow 
Editorial  http://discuss.codechef.com/problems/RESIST 
Tags  cook21, easy, flying_ant 
Date Added:  3042012 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions