NG0FRCTN - Fractions on Tree


A fraction tree is an infinite binary tree  defined as follows:

1)Every node of tree contains a fraction

2)Root of tree contains the fraction 1/1

3)Any node with fraction i/j has two children : left child with fraction i/(i+j) and right child with fraction (i+j)/j           

For example , fraction tree upto 3 levels is as shown:

Fraction tree upto 3 levels

We number the nodes according to increasing levels ( root is at level 1) and at any same level , nodes are numbered from left to right. So first node holds the fraction 1/1 , second one holds 1/2 , third one holds 2/1 fourth one holds 1/3 and so on.


Your task is simple. Given a number n , you are to find the fraction at the nth node.

 

Input

Every line of the input contains a single number n. You are to find the fraction at nth node of fraction tree. Input file terminates with a 0 which is not to be processed.

 

Output

For each input , print numerator and denominator of the lowest form of the fraction seperated by a /. Output of each case to be done in seperate lines.

Example

Input:
1
2
3
7
0

Output:
1/1
1/2
2/1
3/1

Constraints : 1<= # of test cases <=30000 1<=N<=10^10
1
1
uQs
+
Q
Q
Q
Q
Q
Q
Q
Q
Q








1 
2 u
e
e
e
e
e
e
%
%
%
%
%
%
2
u1
e
e
e
e
e
e
%
%
%
%
%
1 %
3
u
A
A
A
A
A
A






3
2
uA
A
A
A
A
A






2
3
uA
A
A
A
A
A






3
1
uA
A
A
A
A
A





1 
4
uA
A


4
3
uA
A


3
5
uA
A


5
2
uA
A


2
5
uA
A


5
3
uA
A


3
4
uA
A


4
1
uA

hide comments
spoj2121: 2015-12-01 13:53:22

try for a O(T*logn) solution its is easy to implement

krish: 2015-04-22 12:57:01

10000000000
ans:7271/77695
10^8
ans:897/7901

Francky: 2014-12-29 16:00:53

(29/12/2014) Image uploaded, and now visible.

Martijn Muijsers: 2013-10-18 13:25:03

Tested all possible cases with Wolfram API, all correct. Getting wrong answer :S Could you possibly check 10287391? :)

Sidharth Guglani: 2012-08-29 22:41:31

getting WA don't know why passing all the test cases on the forum.
please check my solution id 7557575

EDIT : ACC..

Last edit: 2013-01-30 06:13:08
Shubham: 2012-08-22 17:19:28

too tough in python :\
the problem would be tricky if initially it were not 1/1

well i am lagging: 2012-02-06 18:01:18

image is not visible please fix the problem

Santiago Palacio: 2012-01-09 22:02:33

Image is not really necessary, i believe.

Ajey Golsangi: 2012-01-05 10:12:55

Image not visible. Please correct the problem.

[Retired] Fendy Kosnatha: 2011-03-29 02:41:53

image is visible, please updated...


Added by:Nikhil Garg
Date:2009-12-19
Time limit:1.440s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own