NOVICE44 - Problem 4

no tags 

 

Piyush is a very inteligent chap, he has a facination for maths and is never convinced without proof of anything. Last time I told him that sqrt(2) can be written as an expansion of a series as sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
Now i need to prove this to him. Being a fan of finding all solutions i have descided to use a program to find all possible fractions that can be formed using this series with depth = N and show it to piyush, I need your help to do this.
example:
N=1 : 1 + 1/2 = 3/2
N=2 : 1 + 1/(2 + 1/2) = 7/5
N=3 : 1 + 1/(2 + 1/(2 + 1/2)) = 17/12
and so on...
Given a value of N(<=40) print the fraction in lowest form. Lowest form means that GCD(numerator,denominator) = 1

Piyush is a very inteligent chap, he has a facination for maths and is never convinced without proof of anything. Last time I told him that sqrt(2) can be written as an expansion of a series as sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

Now I need to prove this to him. Being a fan of finding all solutions I have descided to use a program to find all possible fractions that can be formed using this series with depth = N and show it to piyush, I need your help to do this.

example:

N=1 : 1 + 1/2 = 3/2

N=2 : 1 + 1/(2 + 1/2) = 7/5

N=3 : 1 + 1/(2 + 1/(2 + 1/2)) = 17/12

and so on...

Given a value of N(<=40) print the fraction in lowest form. Lowest form means that GCD(numerator,denominator) = 1

Input

line 1: T(number of test cases)

line 2 to T+1: vaue of N for each test case

Output

numerator/denominator in the lowest form for each test case

Example

Input:
4
1
2
3
4

Output:
3/2
7/5
17/12
41/29


Added by:Mahesh Chandra Sharma
Date:2011-03-01
Time limit:0.545s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem