Continued Fractions

Let b[0], b[1], b[2], ..., b[n] be integers with b[k] > 0 for k > 0. The continued fraction of order n with coefficients b[1], b[2], ..., b[n] and the initial term b[0] is defined by the following expression

which can be abbreviated as [b[0]; b[1], ..., b[n]].

An example of a continued fraction of order n = 3 is [2;3,1,4]. This is equivalent to

Write a program that determines the expansion of a given rational number as a continued fraction. To ensure uniqueness, make b[n] > 1.

Input

Consists of an undetermined number of rational numbers. Each rational number is defined by two integers, numerator and denominator.

Output

For each rational number output the corresponding continued fraction on a separate line.

Examples