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


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

hide comments
2020-08-05 13:21:31
cakewalk :)
2015-12-01 13:53:22
try for a O(T*logn) solution its is easy to implement
2015-04-22 12:57:01 krish
10000000000
ans:7271/77695
10^8
ans:897/7901
2014-12-29 16:00:53 Francky
(29/12/2014) Image uploaded, and now visible.
2013-10-18 13:25:03 Martijn Muijsers
Tested all possible cases with Wolfram API, all correct. Getting wrong answer :S Could you possibly check 10287391? :)
2012-08-29 22:41:31 Sidharth Guglani
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
2012-08-22 17:19:28 Shubham
too tough in python :\
the problem would be tricky if initially it were not 1/1
2012-02-06 18:01:18 well i am lagging
image is not visible please fix the problem
2012-01-09 22:02:33 Santiago Palacio
Image is not really necessary, i believe.
2012-01-05 10:12:55 Ajey Golsangi
Image not visible. Please correct the problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.