Shortening codes

Given a continued fraction 'a₀ a₁ a₂...a_n' with a_i<=32767 calculate the representing rational number 'p/q' with p and q being coprime. Otherwise given the rational number 'p/q' with 0<=p<=32767, 0<q<=32767 calculate the representing continued fraction 'a₀ a₁ a₂...a_n' with a_n>1 if n>0. There are no negative numbers.

Input

In the first line the number of test cases t<100. Then t lines with either a continued fraction or a rational number. No line is longer then 80 bytes without the linefeed.

Output

t lines with either a representing rational number or continued fraction.

Example

Input:
4
41/152
1 2 3 4
9/4
2 3 7

Output:
0 3 1 2 2 2 2
43/30
2 4
51/22