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:
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
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:
20151201 13:53:22
try for a O(T*logn) solution its is easy to implement


krish:
20150422 12:57:01
10000000000


Francky:
20141229 16:00:53
(29/12/2014) Image uploaded, and now visible. 

Martijn Muijsers:
20131018 13:25:03
Tested all possible cases with Wolfram API, all correct. Getting wrong answer :S Could you possibly check 10287391? :) 

Sidharth Guglani:
20120829 22:41:31
getting WA don't know why passing all the test cases on the forum.


Shubham:
20120822 17:19:28
too tough in python :\


well i am lagging:
20120206 18:01:18
image is not visible please fix the problem 

Santiago Palacio:
20120109 22:02:33
Image is not really necessary, i believe. 

Ajey Golsangi:
20120105 10:12:55
Image not visible. Please correct the problem. 

[Retired] Fendy Kosnatha:
20110329 02:41:53
image is visible, please updated... 
Added by:  Nikhil Garg 
Date:  20091219 
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 