관람차 (큰 입력)

관람차에는 곤돌라 $N$개가 원형으로 달려 있고, 관람차는 천천히 돈다. 곤돌라는 입구를 하나씩 지나가고, 입구에서 기다리던 손님은 지나가는 곤돌라에 탈 수 있다.

곤돌라 하나에는 한 명만 탄다. 입구를 지나는 곤돌라에 이미 사람이 타고 있으면 손님은 다음 곤돌라를 기다리고, 그 곤돌라에도 사람이 있으면 또 그다음 곤돌라를 기다린다. 빈 곤돌라가 올 때까지 이 과정을 되풀이한다. 이 문제에서 곤돌라에서 내리는 사람은 없다. 한 번 탄 사람은 그대로 관람차와 함께 계속 돈다.

요금은 기다린 만큼 달라진다. 입구를 처음 지나는 곤돌라가 비어 있으면 손님은 $N$달러를 낸다. 그 곤돌라에 사람이 있어서 두 번째 곤돌라를 기다려야 하면 $N-1$달러를 낸다. 앞의 두 곤돌라에 사람이 있어서 세 번째 곤돌라에 타면 $N-2$달러를 낸다. 일반적으로 사람이 타고 있는 곤돌라 $K$개를 그냥 보낸 손님은 $N-K$달러를 낸다. 가장 나쁜 경우에는 하나만 남기고 모든 곤돌라를 보내므로 1달러만 낸다.

손님이 오는 시각은 무작위다. 따라서 각 손님 앞을 처음 지나는 곤돌라는 곤돌라 $N$개 중에서 균등하게 정해지고, 손님마다 서로 독립이다. 앞 손님이 아직 타지 못한 동안에는 새 손님이 오지 않으므로 줄은 생기지 않는다. 손님은 언제나 자기 앞을 지나는 첫 번째 빈 곤돌라에 탄다.

곤돌라의 개수와 이미 사람이 타고 있는 곤돌라가 주어진다. 모든 곤돌라가 찰 때까지 받는 요금 총액의 평균을 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 $T$개의 줄에는 테스트 케이스가 한 줄에 하나씩 주어지며, 각 줄은 '.'(마침표)와 'X'(대문자 X)로만 이루어진다. 이 줄의 길이가 $N$이다. $i$번째 문자가 'X'이면 $i$번 곤돌라에 이미 사람이 타고 있고, '.'이면 아직 비어 있다. 곤돌라 번호는 입구를 지나는 순서를 따른다. 1번 곤돌라 다음에 2번 곤돌라가 오고, 마지막 곤돌라 다음에는 다시 1번 곤돌라가 온다.

• $1 \le T \le 50$
• $1 \le N \le 200$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 받는 요금 총액의 평균이다. $y$는 소수점 아래 여섯 자리까지 반올림해서 출력한다.

.X.의 답이 나오는 과정은 다음과 같다. 곤돌라는 세 개이고 2번에 사람이 타고 있으므로 손님 두 명이 오고, 각 손님 앞을 처음 지나는 곤돌라는 세 가지다. 따라서 확률이 각각 $1/9$인 아홉 가지 경우가 나온다.

첫 손님 앞을 1번 곤돌라가 처음 지나가면 그 곤돌라가 비어 있으므로 첫 손님은 3달러를 낸다. 이어서 둘째 손님이 온다.

• 둘째 손님 앞을 1번 곤돌라가 처음 지나가면 1번과 2번 모두 차 있으므로 3번에 타고 1달러를 낸다. 합계 4달러.
• 둘째 손님 앞을 2번 곤돌라가 처음 지나가면 2번이 차 있으므로 3번에 타고 2달러를 낸다. 합계 5달러.
• 둘째 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 비어 있으므로 3달러를 낸다. 합계 6달러.

첫 손님 앞을 2번 곤돌라가 처음 지나가면 2번이 차 있으므로 첫 손님은 3번에 타고 2달러를 낸다. 이어서 둘째 손님이 온다.

• 둘째 손님 앞을 1번 곤돌라가 처음 지나가면 1번이 비어 있으므로 3달러를 낸다. 합계 5달러.
• 둘째 손님 앞을 2번 곤돌라가 처음 지나가면 2번과 3번 모두 차 있으므로 1번에 타고 1달러를 낸다. 합계 3달러.
• 둘째 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 차 있으므로 1번에 타고 2달러를 낸다. 합계 4달러.

첫 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 비어 있으므로 첫 손님은 3달러를 낸다. 이어서 둘째 손님이 온다.

• 둘째 손님 앞을 1번 곤돌라가 처음 지나가면 1번이 비어 있으므로 3달러를 낸다. 합계 6달러.
• 둘째 손님 앞을 2번 곤돌라가 처음 지나가면 2번과 3번 모두 차 있으므로 1번에 타고 1달러를 낸다. 합계 4달러.
• 둘째 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 차 있으므로 1번에 타고 2달러를 낸다. 합계 5달러.

아홉 가지 가운데 3달러를 받는 경우가 하나, 4달러가 셋, 5달러가 셋, 6달러가 둘이므로 평균은 $(1 \times 3 + 3 \times 4 + 3 \times 5 + 2 \times 6)/9 = 42/9 = 4.666666\ldots$달러다.