NG1FRCTN - Fractions on Tree ( reloaded !)

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, as always! Given two numbers a and b, you are to find the product of fractions at all those nodes whose number is between a and b both inclusive.

Input

Every line of the input contains two numbers a and b separated by a space. You are to find the product of all fractions which are at node having number between a and b both inclusive. Input file terminates with a 0 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 on separate lines.

Example

Input:
1 1
1 2
2 4
0 0

Output:
1/1
1/2
1/3

Constraints

1 <= T <= 30000

1 <= a <= b <= 10^10


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

hide comments
2019-05-02 05:50:01
Francky, please link the same image you did in NG0FRCTN if you can read this.

Really enjoyed both of the problems, thanks to the psetter.
2013-12-27 09:49:39 anurag garg
try to find the logic upto level 5
no need to go further
2012-04-05 11:16:32 a.out
getting WA :(
2011-01-21 09:16:31 VinyleEm
Image isn't visible. Please put up a new one.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.