Chef and Ridges

All submissions for this problem are available.
###Read problems statements [Hindi](http://www.codechef.com/download/translated/NOV18/hindi/PRDRG.pdf) , [Vietnamese](http://www.codechef.com/download/translated/NOV18/vietnamese/PRDRG.pdf) , [Mandarin Chinese](http://www.codechef.com/download/translated/NOV18/mandarin/PRDRG.pdf) , [Russian](http://www.codechef.com/download/translated/NOV18/russian/PRDRG.pdf) and [Bengali](http://www.codechef.com/download/translated/NOV18/bengali/PRDRG.pdf) as well. We have a rectangular piece of cardboard with width $1$ (its height is not important). We are going to fold it in the following way:  pick up the right side of the piece of cardboard and move it to the left until it touches the left side  this way, a smaller piece of cardboard with width $1/2$ is created; if we unfolded it, we could see a vertical ridge formed in the middle  pick up the left side of this new piece of cardboard and move it to the right until it touches the (new) right side  pick up the right side of the resulting piece of cardboard and move it to the left until it touches the left side, etc. Whenever the cardboard is folded, exactly one of its new sides is a newly formed ridge (there may be more, internal ridges formed, but we do not consider these). Let's denote such a ridge created in the $k$th folding by $R_k$. In total, we fold the piece of cardboard $N$ times. Afterwards, we unfold it and look at the formed ridges. Let's denote the distance of ridge $R_N$ (i.e. the last formed outer ridge) from the left side of the original piece of cardboard by $D_N$. For example, $D_1 = 1/2$ and $D_2 = 1/4$. It is possible to express $D_N$ as an irreducible fraction $x/y$. Find this fraction. Assume that it is possible to fold the piece of cardboard as many times as we want. ### Input The first and only line of the input contains a single integer $T$ denoting the number of test cases. For each test case, a space and an integer $N$ follows. ### Output Print a single line containing $2T$ spaceseparated integers. For the $i$th test case ($1 \le i \le T$), the $2i1$th and $2i$th integer should denote $x$ and $y$ — the position of the last ridge as an irreducible fraction. ### Constraints  $1 \le T \le 5$  $1 \le N \le 25$ **Subtask #1 (10 points):**  $1 \le T \le 5$  $1 \le N \le 5$ **Subtask #2 (90 points):** original constraints ### Example Input ``` 2 1 2 ``` ### Example Output ``` 1 2 1 4 ``` ### Explanation **Example case 1:** We only fold once, so $x=1$ and $y=2$. **Example case 2:** We fold the piece of cardboard twice. The last edge is at $1/4$, so $x=1$ and $y=4$.Author:  sshhhh 
Editorial  https://discuss.codechef.com/problems/PRDRG 
Tags  gcd, nov18, pattern, simple, simulation, sshhhh, taran_1407 
Date Added:  27092018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 