FAHMY - Fahmy and Fractions

no tags 

Fahmy loves fractions very much, so today he decided to play with them a little. He has N fractions, and he wants to reduce them to just one fraction that represents the sum of all N fractions, but he has some conditions:

  1. The final fraction should be in its simplest form (i.e. there are no common factors between the numerator and the denominator).
  2. If the numerator is greater than the denominator then he writes the integer part before the fraction and subtracts the integer from the fraction (See the example for more clarification).

As he’s a very talented programmer, he managed to write a code for the required program. And he challenges you to do it, too.

Input

The first line will contain T (1 <= T <= 100) – the number of test cases. Each test case starts with a line containing a single integer N (1 <= N <= 10) – the number of fractions, and N-lines containing the fractions in the form "A/B", without the quotes, where (0 <= A <= 100, 1 <= B <= 10).

Output

For each test case, print a single line containing the answer to the problem in the form "X/Y" (Without the quotes). Or in the form "A X/Y" (Without the quotes), if the numerator is greater than the denominator in the form "X/Y", where A, X and Y are all positive integers.

Example

Input:
3
1
2/4
2
1/2
3/5
2
2/4
3/9 Output: 1/2
1 1/10
5/6 

hide comments
Simes: 2023-04-09 11:25:59

The expected answer for 1/2 + 1/2 is 1 0/1


Added by:eagle93
Date:2014-06-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64