Submit | All submissions | Best solutions | Back to list |

## CONTFRAC - Continued fraction |

Given a continued fraction 'a_{0} a_{1} a_{2}...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_{0} a_{1} a_{2}...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 7Output:0 3 1 2 2 2 2

43/30

2 4

51/22

Added by: | HWK |

Date: | 2011-06-24 |

Time limit: | 0.100s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: SCM qobi |