I I U P C   2 0 1 4

Problem E: Risk of Trading

 

Once upon a time, there were two great countries separated by a great river. They were called East country and West country. There were many great cities in both countries. And trading between them was profitable. Everybody lived in peace, but everything changed when the fire pirates attacked. They intercepted the ships across the river and looted them.

 

Then a big trading company got in trouble. There were N cities in both of the countries. And there was a ship in each of the N cities of West countries. They wanted to send each of the N ships to one of the different cities of the East country. Thus, after the voyage, each of the N cities in the East country would have one of the ships. But the pirates were in the river. And they could attack any ship. Even if one of the ships got attacked, the company would have faced great problems. Now from the reports of pirates attack, they had calculated the risks of sending a ship from each of the cities of West country to each of the cities of East country. They just needed to find a safe pairing between each N cities of West country to one of the N city of East country such that the risk of even one of the ships get attacked would be minimum. Could you help them?

 

 

Input

First line of the input is T (T≤20), which is the number of test cases in input. Then T test cases follow. In each of the test case the first line of the input is N (1≤N≤40) the number of cities in each countries. Then next N lines are for each of the cities of West country. In ith line, there are N probabilities; jth of this is the probability of getting attacked by pirates if they sail from ith city of West country to the jth city of East country. The probabilities are given in fraction form in a/b format where 0≤a≤b≤40 and a/b is in irreducible format (i.e. a and b is co-prime).

 

Output

For each of the cases, print the minimum probability of one the ship getting attacked by the pirates. Final answer's a and b will fit in a signed 64 bit integer number (long long in C/C++, long in Java).

Sample Input

Output for the Sample Input

2

2

1/2 1/2

1/4 3/4

2

1/8 7/8

0/1 1/15

5/8

22/120

 

Problem Setter: Ridowan Muhammad

Alternate Solution: Bidhan Roy

 

 

 

 

Output Explanation

 

In the both cases there can be two type of pairing,

·City 1 of West country to city 1 of East and city 2 of West country to city 2 of East.

·City 1 of West country to city 2 of East and city 2 of West country to city 1 of East.

 

In first pairing,

·The probability of the ship from city 1 of West getting attack but not the ship from city 2 is 1/2 * ( 1 – 3/4 ) = 1/2 * 1/4 = 1/8.

·The probability of the ship from city 2 of West getting attack but not the ship from city 1 is ( 1 – 1/2 ) *  3/4 = 1/2 * 3/4 = 3/8.

·The probability of both of the ship getting attacked is 1/2 * 3/4 = 3/8.

So total risk of one of the ships getting attacked is 1/8 + 3/8 + 3/8 = 7/8.

 

In second pairing the risk is 1/2 * ( 1 – 1/4 ) + ( 1 – 1/2 ) * 1/4 + 1/2 * 1/4 = 3/8 + 1/8 + 1/8 = 5/8.

 

So the second pairing gives minimum risk 5/8.

 

In the second example, for the first pairing risk is 1/8 * ( 1 – 1/15 ) + ( 1 – 1/8 ) * 1/15 + 1/8 * 1/5 = 14/120 + 7/120 + 1/120 = 22/120 = 11/60.

For the second pairing risk is 7/8 as the ship from city 2 of west to city 1 of East will go risk free(0/1 = 0 risk). But 11/60<7/8 so the answer is 11/60.