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 up to 3 levels is as shown:

Fraction tree up to 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 separated by a /. Output of each case to be done in separate lines.

Example

Input:
1
2
3
7
0

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

Constraints

1 <= number of test cases <= 30000, 1 <= N <= 10^10


hide comments
kumar_anubhav: 2020-08-05 13:21:31

cakewalk :)

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.


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