속임수 전쟁 (Large)

나오미와 켄은 가끔 함께 게임을 한다. 게임을 시작하기 전에 두 사람은 겉모습이 똑같은 나무 블록을 N개씩 받는다. 블록의 질량은 0.0kg보다 크고 1.0kg보다 작으며, 모든 블록의 질량은 서로 다르다. 이 블록으로 할 수 있는 게임은 많지만 두 사람이 보통 하는 것은 "전쟁"이라고 부르는 게임이다. 전쟁의 규칙은 다음과 같다.

1. 두 사람은 자기 블록의 질량을 모두 잰다. 그래서 자기 블록의 질량은 전부 알지만 상대 블록의 질량은 모른다.
2. 다음 과정을 N번 반복한다.
   1. 나오미가 자기 블록 하나를 고른다. 그 질량을 ChosenNaomi라고 하자.
   2. 나오미가 고른 블록의 질량을 켄에게 말한다.
   3. 켄이 자기 블록 하나를 고른다. 그 질량을 ChosenKen이라고 하자.
   4. 두 사람은 고른 블록을 양팔 저울의 양쪽에 하나씩 올린다. 더 무거운 블록을 낸 사람이 1점을 얻는다.
   5. 두 블록은 모두 불에 타 사라진다.

나오미는 세 가지를 깨달았다. 첫째, 자신이 자주 진다. 둘째, 나오미의 전략을 전혀 가정하지 않고도 켄이 자기 점수를 최대로 만드는 유일한 전략이 있으며, 켄은 언제나 그 전략을 쓴다. 셋째, 자신은 지는 것을 몹시 싫어한다. 그래서 나오미는 전쟁 대신 "속임수 전쟁"이라고 부르는 게임을 하기로 했다. 속임수 전쟁의 좋은 점은 켄이 여전히 전쟁을 하고 있다고 믿는다는 것이다.

속임수 전쟁의 규칙은 다음과 같다. 전쟁과 달라지는 부분은 굵게 표시했다.

1. 두 사람은 자기 블록의 질량을 모두 잰다. 나오미는 켄이 보지 않을 때 켄의 블록도 재 두어서 모든 블록의 질량을 안다. 켄은 자기 블록의 질량만 안다.
2. 다음 과정을 N번 반복한다.
   1. 나오미가 자기 블록 하나를 고른다. 그 질량을 ChosenNaomi라고 하자.
   2. 나오미는 0.0kg보다 크고 1.0kg보다 작은 수 ToldNaomi를 켄에게 말한다. 전쟁을 하고 있다고 믿는 켄은 방금 들은 수가 ChosenNaomi라고 생각한다.
   3. 켄이 자기 블록 하나를 고른다. 그 질량을 ChosenKen이라고 하자.
   4. 두 사람은 고른 블록을 양팔 저울의 양쪽에 하나씩 올린다. 더 무거운 블록을 낸 사람이 1점을 얻는다.
   5. 두 블록은 모두 불에 타 사라진다.

나오미는 자신이 전쟁을 하고 있지 않다는 사실을 켄이 눈치채지 않기를 바란다. 그래서 낼 블록과 켄에게 말할 수를 정할 때, 저울이 ChosenNaomi와 ToldNaomi가 다르다는 사실을 드러내지 않도록 해야 한다. 즉 다음 두 조건을 지키도록 결정해야 한다.

• ChosenNaomi > ChosenKen인 것과 ToldNaomi > ChosenKen인 것은 서로 필요충분조건이다.
• ToldNaomi는 켄이 가진 어떤 블록의 질량과도 같으면 안 된다. 그런 일은 불가능하다는 것을 켄이 알기 때문이다.

켄이 속임수를 알아챌 수도 있으니 나오미가 속임수로 점수를 더 얻지는 못할 것처럼 보인다. 하지만 나오미는 두 사람 모두 전쟁을 하고 있다고 켄이 믿는다는 것을 알고, 켄이 무엇을 아는지도 알며, 켄이 항상 전쟁의 유일한 최적 전략을 따른다는 것도 안다. 그래서 켄이 무엇을 낼지 언제나 예측할 수 있다.

나오미와 켄이 처음에 가진 블록의 질량이 주어진다. 나오미는 점수를 최대로 얻도록 속임수 전쟁을 최적으로 한다. 켄은 두 사람 모두 전쟁을 하고 있다는 가정 아래 자기 점수를 최대로 얻도록 전쟁을 최적으로 한다. 나오미의 점수는 몇 점인가? 그리고 나오미가 대신 전쟁을 최적으로 했다면 몇 점이었겠는가?

규칙 설명

각자 블록이 하나씩 남았고 나오미가 0.5kg, 켄이 0.6kg를 가지고 있다면 점수는 반드시 켄이 얻는다. 나오미는 0.6kg보다 크거나 같은 수를 말할 수 없다. 그런 수를 말하면 저울이 켄의 블록이 더 무겁다고 보여 주는 순간 켄은 나오미가 전쟁을 하고 있지 않다는 것을 알게 된다.

각자 블록이 두 개씩 남았고 나오미가 0.7kg과 0.2kg, 켄이 0.8kg과 0.3kg를 가지고 있다고 하자. 나오미는 0.2kg 블록을 내면서 0.6kg짜리 블록을 골랐다고 켄을 속일 수 있다. 켄은 전쟁의 규칙대로 나오미가 사실을 말했다고 보고 0.8kg 블록을 내서 1점을 얻는다. 켄은 속았지만 그 사실을 끝내 알지 못한다. 저울이 켄의 예상대로 0.8kg 블록이 더 무겁다고 보여 주기 때문이다. 이제 나오미는 0.7kg 블록을 내고 그 질량을 그대로 0.7kg이라고 말해 1점을 얻는다. 나오미가 속임수 전쟁 대신 전쟁을 했다면 켄이 2점, 나오미가 0점을 얻었을 것이다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 각 사람이 가진 블록의 개수 N이 주어진다. 다음 줄에는 나오미가 가진 블록의 질량 N개가 kg 단위 실수로 공백을 사이에 두고 주어진다. 마지막 줄에는 켄이 가진 블록의 질량 N개가 같은 형식으로 주어진다.

나오미와 켄에게 주어지는 질량은 모두 0 뒤에 소수점이 오고 그 뒤에 1자리에서 5자리까지의 숫자가 오는 형태다. 입력의 모든 수가 소수점 아래 1자리에서 5자리까지라는 사실을 켄과 나오미는 모른다. 그래서 나오미는 질량이 0.5000001kg인 블록을 냈다고 켄에게 말할 수 있고, 켄에게는 그 말을 믿지 않을 이유가 없다.

제한

• $1 \le T \le 50$
• $1 \le N \le 1000$
• 나오미와 켄에게 주어지는 질량은 모두 서로 다르고, 0.0보다 크고 1.0보다 작다.

각 테스트 케이스마다 "Case #x: y z" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호, y는 나오미가 속임수 전쟁을 최적으로 했을 때 얻는 점수, z는 나오미가 전쟁을 최적으로 했을 때 얻는 점수다.