시험 통과 확률 (대형 입력)

데이브는 사지선다형 시험을 온라인으로 치른다. 답안은 여러 번 제출할 수 있지만, 모든 문항을 맞힌 제출이 하나라도 있어야 합격한다. 한 번 제출할 때 모든 문항에 답을 적어야 하고, 제출한 뒤에 알 수 있는 것은 합격 여부뿐이다.

데이브는 문항마다 네 보기가 각각 정답일 확률을 추정해 두었다. 이 확률은 다른 문항에 무엇을 적었는지와 독립이다. 제출 횟수가 정해져 있을 때, 데이브는 합격 확률이 가장 커지도록 답안을 고른다.

데이브가 최적으로 답안을 고를 때의 합격 확률을 구하라.

첫 줄에 테스트 케이스의 개수 $C$가 주어진다. 이어서 $C$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 데이브가 제출할 수 있는 횟수 $M$과 시험의 문항 수 $Q$가 주어진다. 다음 $Q$개의 줄에는 각 문항의 보기 네 개가 정답일 확률이 차례로 주어진다. 확률은 모두 0 이상이고 소수점 아래 최대 여섯 자리까지 주어지며, 한 줄에 있는 네 확률의 합은 1이다.

제한

• $1 \le C \le 100$
• $1 \le Q \le 30$
• $1 \le M \le 10000$

각 테스트 케이스마다 한 줄에 Case #X: Y를 출력한다. $X$는 테스트 케이스 번호이고 1부터 시작한다. $Y$는 최대 합격 확률이며, 소수점 아래 여섯 자리로 반올림해 항상 여섯 자리를 채워 출력한다. 확률이 정확히 $0.5$라면 0.500000으로 출력한다.