SPOJ Problem Set (classical)

5640. Fractions on Tree

Problem code: NG0FRCTN

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<=T <=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

Added by:	Nikhil Garg
Date:	2009-12-19
Time limit:	3s
Source limit:	50000B
Languages:	All except: TECS
Resource:	own