IITWPC4J  Gopu and Fishes
Gopu is playing with fishes, He likes playing them very much because they are lovely creatures. There are n fishes, All the n fishes are kept in n aquariums. Each fish is kept in different aquarium.
While he is playing with them, there comes a magic instant in his play. At that instant, fish in aquarium i can go to aquarium j with probability p[i][j]. At this magic instant, all the fishes go to aquariums according to their probabilities.
Now there is a slight issue in this, If more than one fishes land on the same aquarium, Then they can not survive because of lack of space. You have to find the probability that none of Gopu's fishes dies, otherwise he would be very sad.
Please help our little Gopu so that he could keep playing with his fishes :)
Input
First line contains number of test cases : T (1 <= T <= 1000)
Next line contains n : number of fishes (1 <= n <= 15).
For next n lines, each line contains n space seperated real numbers. In line i, jth number is p[i][j]. p[i][j] is precise upto 6 decimal digits.
Output
For each test case, print the probability that none of Gopu's fishes dies. (probability is a real number and it should not have error more than 1e6), That is your answer should be correct upto 6 decimal digits.
Example
Input: 2
2
1 0
0 1
2
0.5 0.5
0.5 0.5 Output: 1.000000
0.500000
hide comments
tushar97:
20170707 20:15:48
can anyone give any test cases for this? I'm getting wrong answer.


dark_lord1:
20160331 22:33:10
Last edit: 20160331 22:33:37 

dark_lord1:
20160331 22:33:10
Same algorithm in C++ got TLE, in C got AC...Wierd


mr_lazy:
20150901 11:19:59
AC in go! .. Can't mention my happiness! ^_^ 

vtcb:
20140528 14:23:14
Any critical cases? 

praveen123:
20140313 06:34:12
@Piyush, I have updated the judge now, Sorry for inconvience :( 

Piyush Kumar:
20140313 06:32:34
I think testing judge with relative error 10^6 would be better than exact judge (I'm guessing you're using exact judge now because printf("%.9lf") gave WA while printf("%.6lf") got accepted) Last edit: 20140227 06:39:24 

praveen123:
20140313 06:32:34
^Flago, Yes it is fast enough :) But still it might not allow java to pass, so updated time limit to 10 secs :) 

Flago:
20140313 06:32:34
After getting TLE in php, I tried it in C++, still TLE.

Added by:  praveen123 
Date:  20140203 
Time limit:  1s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 