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 1e-6), 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: 2017-07-07 20:15:48

can anyone give any test cases for this? I'm getting wrong answer.

dark_lord1: 2016-03-31 22:33:10

Last edit: 2016-03-31 22:33:37
dark_lord1: 2016-03-31 22:33:10

Same algorithm in C++ got TLE, in C got AC...Wierd
Submitted both without fast i/o
Costed me one TLE

mr_lazy: 2015-09-01 11:19:59

AC in go! .. Can't mention my happiness! ^_^

vtcb: 2014-05-28 14:23:14

Any critical cases?

praveen123: 2014-03-13 06:34:12

@Piyush, I have updated the judge now, Sorry for inconvience :(

Piyush Kumar: 2014-03-13 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: 2014-02-27 06:39:24
praveen123: 2014-03-13 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: 2014-03-13 06:32:34

After getting TLE in php, I tried it in C++, still TLE.
Isn't O(N*2^N) fast enought for N<=15 ?.. With C++ on ideone, time: 0.04 for N=16
I'm confused... Any thought ?

Last edit: 2014-02-06 16:34:43

Added by:praveen123
Date:2014-02-03
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge